Merge sort y quick sort: ordenar de verdad en O(n log n)
Los algoritmos de ordenación sencillos son O(n²) y se ahogan con muchos datos. Aquí llegan los que sí se usan en serio: merge sort y quick sort, los dos O(n log n), los que están metidos por dentro de casi todos los lenguajes cuando llamas a una función de ordenar. En esta cuarta entrega de la serie de Algoritmos te explico cómo funcionan los dos con la estrategia de divide y vencerás: el merge sort, que parte la lista hasta el fondo y la recompone ordenada, estable y fiable; y el quick sort, que elige un pivote y reparte alrededor, más rápido en la práctica pero con un peor caso O(n²) que conviene conocer. Verás por qué O(n log n) es la frontera de la ordenación por comparación y qué usa cada lenguaje por debajo.