En este tutorial aprenderemos una de las mejores formas de ordenar arreglos, merge es un algoritmo eficiente basado en recursion que divide en partes el arreglo para posteriormente ordenarlo.

Estructura base

function mergeSort(items) {

  if (items.length < 2) {

    return items;

  }



  var middle = Math.floor(items.length / 2),

      left = items.slice(0, middle),

      right = items.slice(middle);



  return merge(mergeSort(left), mergeSort(right));

}

Crearemos una función llamada mergeSort que recibe como parámetro un array, dentro de la función tenemos una condición, si el array tiene un tamaño menor a dos (que solo tenga un item) regresamos el array, si la condición es falsa entonces buscamos la mitad del array y lo almacenamos en la variable middle después con la ayuda de slice dividimos el array en dos mitades, izquierda y derecha, al final regresamos una nueva función llamada merge que recibe dos arrays, como podemos notar en merge(mergeSort(left), mergeSort(right)) lo que hacemos es aplicar la recursión en mergeSort a la hora de pasar los arrays a merge.

function merge(left, right) {

  var result = [],

      il = 0,

      ir = 0;

  //il, ir indices de los arrays



  //recorremos los arrays hasta que lleguemos al final de uno

  while(il < left.length && ir < right.length) {

    if (left[il] < right[ir]) {

      result.push(left[il++]);

      //si el item del array left es menor

      //este se agrega a la lista y se aumenta en uno su indice (il)

    } else {

      //si el item de right es menor este se agrega a la lista e igualmente su indice crece

      result.push(right[ir++]);

    }

  }

  return result.concat(left.slice(il)).concat(right.slice(ir));

}

La función merge recorre los arrays con un ciclo while, compara cada item del array y va guardando el mas pequeño en una nueva lista hasta que llegamos al final de alguno de los arrays, puede pasar que a una de las listas les falten items por recorrer, esto se soluciona agregándolos al final con slice ya que con las variables il ir vamos contando los indices de los arrays, si faltan slice se encarga de agregarlos.

Podemos correr el código:

var arr = [1, 5, 2, 7]

console.log(mergeSort(arr));

y tener el array ordenado.