Algunas notas sobre el ordenamiento por mezcla

Algunas notas acerca del algoritmo de Ordenamiento por Mezcla.

Descripción

Algoritmo recursivo fundamentado en la estrategia «divide y vencerás». Dos componentes principales:

• Una función para separar listas recursivamente hasta que recibe un único elemento.
• Una función que combina dos elementos ya ordenados en una lista ordenada.

Complejidad temporal

Pseudocódigo

Implementación en Rust

pub fn merge_sorted_arrays(left: Vec<i32>, right: Vec<i32>) -> Vec<i32> {
  let left_length = left.len();
  let right_length = right.len();

  // El array resultante tendr el tamao de los dos arrays que se pasen
  let mut sorted_items = vec![0; left_length + right_length];

  let mut i = 0;
  let mut j = 0;

  // Iterar sobre el array que vamos a rellenarcon elementos de los arrays 
  // izquierdo o derecho
  for k in 0..sorted_items.len() {
    // Si ninguno de los punteros "i" ni "j" han llegado a su lmite
    if i + 1 <= left.len() && j + 1 <= right.len() {
      // Decidir entre el elemento actual del array izquierdo 
      // y el elemento actual del array derecho cul de los dos ser 
      // el siguiente para el array final
      if left[i] <= right[j] {
        sorted_items[k] = left[i];
        i = i + 1;
      } else if left[i] > right[j] {
        sorted_items[k] = right[j];
        j = j + 1;
      }
    } else if i + 1 <= left.len() {
      // Si slo el puntero "i" no ha alcanzado el lmite 
      // y por tanto "j" lo ha hecho
      sorted_items[k] = left[i];
      i = i + 1;
    } else if j + 1 <= right.len() {
      // Si slo el puntero "j" no ha alcanzado el lmite 
      // y por tanto "i" lo ha hecho
      sorted_items[k] = right[j];
      j = j + 1;
    }
  }

  sorted_items
}

pub fn sort_array(unsorted_array: &Vec<i32>) -> Vec<i32> {
  let n = unsorted_array.len();
  if n <= 1 {
    // Caso base: si el input es de longitud 1, 
    // entonces est ya ordenado: devolverlo
    let sorted_array = unsorted_array.to_vec();
    sorted_array
  } else {
    // Si el input es de longitudo dos o mayor
    // 1. Separarlo
    let (left, right) = unsorted_array.split_at(n / 2);
    let left_vec = left.to_vec();
    let right_vec = right.to_vec();

    // 2. Ordenarlo recursivamente
    let left_sorted = sort_array(&left_vec);
    let right_sorted = sort_array(&right_vec);
    let sorted_array_1 = merge_sorted_arrays(left_sorted, right_sorted);
    sorted_array_1
  }
}

fn main() {
  let unsorted_array: Vec<i32> = vec![2, 1, 4, 3];
  let sorted_array = sort_array(&unsorted_array);
  println!("unsorted_array: {:?}", unsorted_array);
  println!("sorted_array: {:?}", sorted_array);
}

#[cfg(test)]
mod tests {
  use super::*;

  #[test]
  fn works_with_sorted_arrays() {
    let unsorted_array = vec![1, 2];
    let sorted_array = sort_array(&unsorted_array);
    let expected_result = vec![1, 2];
    assert_eq!(expected_result, sorted_array);
  }

  #[test]
  fn works_with_simple_unsorted_array() {
    let unsorted_array = vec![2, 1];
    let sorted_array = sort_array(&unsorted_array);
    let expected_result = vec![1, 2];
    assert_eq!(expected_result, sorted_array);
  }

  #[test]
  fn works_with_simple_uneven_lenght_arrays() {
    let unsorted_array = vec![2, 1, 3];
    let sorted_array = sort_array(&unsorted_array);
    let expected_result = vec![1, 2, 3];
    assert_eq!(expected_result, sorted_array);
  }

  #[test]
  fn it_works_with_sorted_arrays() {
    let left = vec![1, 2];
    let right = vec![3, 4];
    let merged = merge_sorted_arrays(left, right);
    let expected_result = vec![1, 2, 3, 4];
    assert_eq!(expected_result, merged);
  }

  #[test]
  fn it_works_with_splits() {
    let left = vec![3, 4];
    let right = vec![1, 2];
    let merged = merge_sorted_arrays(left, right);
    let expected_result = vec![1, 2, 3, 4];
    assert_eq!(expected_result, merged);
  }

  #[test]
  fn it_works_with_uneven_length_lists() {
    let left = vec![3, 4, 5];
    let right = vec![1, 2];
    let merged = merge_sorted_arrays(left, right);
    let expected_result = vec![1, 2, 3, 4, 5];
    assert_eq!(expected_result, merged);
  }

  #[test]
  fn it_works_with_single_item_lists() {
    let left = vec![3];
    let right = vec![1];
    let merged = merge_sorted_arrays(left, right);
    let expected_result = vec![1, 3];
    assert_eq!(expected_result, merged);
  }
}