azrael

El algoritmo es básicamente un QuickSort, al revés y usando busqueda binaria.

Proviene de la idea (fundamental) de que ordenar n elementos de un vector, es equivalente a hacer un “merge” de n vectores ordenados de un elemento (un vector ordenado de un elemento, es un elemento desordenado, lógico).

Por lo tanto lo que hallé es la forma de mezclar n vectores ordenados de forma óptima.

Como estaba convencido de que era una generalización de la búsqueda binaria (ya que es ordenación por comparación), no fué “tan” dificil:

Si quieres mezclar n vectores ordenados en un sólo vector ordenado, tan sólo has de coger el vector central, elegir su elemento central como pivote y situarlo dentro de los vectores que se encuentren en el centro de cada mitad. Pero para eso los elementos de los otros vectores tienen que estar ya situados respecto al resto, es recursivo.

Simplificando, cada elemento ha de buscarse únicamente en dos vectores, uno anterior y uno posterior, de forma recursiva y mediante búsqueda binaria y ¡voilá!

He subido a la forja de rediris  los algoritmos que funcionan de lo que llevo escrito .

No es aún, el algoritmo de ordenación definitivo, pero se le acerca.

De momento, el algoritmo más rápido  es poco más o menos igual de rápido que Quicksort, pero se debe exclusivamente a la implementación, pues en ambas implementaciones uso o(n log n) memoria auxiliar (un autentico despilfarro).

Está en camino una implementación con un uso de memoría constante (es decir, un algoritmo in-place), pero requiere bastante trabajo. De momento tengo los algoritmo escritos de forma recursiva, pero “conociendo” a los compiladores, más vale que los escriba de forma iterativa a mano.

Creo que la mejor versión será usando el algoritmo de merge que he llamado (muy original) oMerge (de óptimo).

Una vez que tenga ese algoritmo en su versión iterativa, prescindiré de algoritmos auxiliares, y escribiré un algoritmo con una sola recursión, como el de Quicksort. Pero creo que se puede ir más allá y eliminar esa recursión tambien, ya que al contrario que en quicksort, las llamadas recursivas del algoritmo principal no dependen de las anteriores.

Bueno, el que quiera ya puede probar las diferentes velocidades de los diferentes merges. Trastenado un poquito con el código fuente, tambien los tipos de ordenación, pero ya digo que de momento, no he escrito AÚN nada mucho más rápido que mergesort.

Feliz navidad y feliz año ;).