Ordenamiento por mezcla

En otro caso: • Dividir la lista desordenada en dos sublistas de aproximadamente la mitad del tamaño.

Por ejemplo, sólo será necesario entrelazar cada lista una vez que están ordenadas.

Aunque heapsort tiene los mismos límites de tiempo que merge sort, requiere sólo Θ(1) espacio auxiliar en lugar del Θ(n) de merge sort, y es a menudo más rápido en implementaciones prácticas.

En el lado bueno, merge sort es un ordenamiento estable, paraleliza mejor, y es más eficiente manejando medios secuenciales de acceso lento.

Merge sort es a menudo la mejor opción para ordenar una lista enlazada: en esta situación es relativamente fácil implementar merge sort de manera que sólo requiera Θ(1) espacio extra, y el mal rendimiento de las listas enlazadas ante el acceso aleatorio hace que otros algoritmos (como quicksort) den un bajo rendimiento, y para otros (como heapsort) sea algo imposible.