Funnelsort

---

Funnelsort es un algoritmo de clasificación basado en comparaciones . Es similar a mergesort , pero es un algoritmo ajeno al caché , diseñado para una configuración en la que el número de elementos a ordenar es demasiado grande para caber en un caché donde se realizan las operaciones. Fue introducido por Matteo Frigo, Charles Leiserson , Harald Prokop y Sridhar Ramachandran en 1999 en el contexto del modelo de caché inconsciente . ^{[1] [2]}

En el modelo de memoria externa , el número de transferencias de memoria que necesita para realizar una especie de elementos en una máquina con caché de tamaño y líneas de caché de longitud es , bajo el supuesto de caché alto que . Se ha demostrado que este número de transferencias de memoria es asintóticamente óptimo para tipos de comparación. Funnelsort también logra la complejidad asintóticamente óptima en tiempo de ejecución de .${\ Displaystyle N}$${\ Displaystyle Z}$${\ Displaystyle L}$${\ Displaystyle O \ left ({\ tfrac {N} {L}} \ log _ {Z} N \ right)}$${\ Displaystyle Z = \ Omega (L ^ {2})}$${\ Displaystyle \ Theta (N \ log N)}$

Funnelsort opera en una matriz contigua de elementos. Para ordenar los elementos, realiza lo siguiente:${\ Displaystyle N}$

Funnelsort es similar a la ordenación por fusión en que una cierta cantidad de submatrices se ordenan de forma recursiva, después de lo cual un paso de fusión combina las submatrices en una matriz ordenada. La combinación se realiza mediante un dispositivo llamado k-merger, que se describe en la sección siguiente.

Una k- fusión toma secuencias ordenadas. Tras una invocación de una k-fusión, genera los primeros elementos de la secuencia ordenada obtenida al fusionar las k secuencias de entrada.${\ Displaystyle k}$${\ Displaystyle k ^ {3}}$

En el nivel superior, funnelsort utiliza una fusión en secuencias de longitud e invoca esta fusión una vez.${\ Displaystyle N ^ {1/3}}$${\ Displaystyle N ^ {1/3}}$${\ Displaystyle N ^ {2/3}}$

---