What is "funnelsort"

Funnelsort is a comparison-based sorting algorithm. It was introduced by Frigo, Leiserson, Prokop, and Ramachandran in 1999 in the context of the cache oblivious model. In the external memory model, the number of memory transfers it needs to perform a sort of N items on a machine with cache of size Z and cache lines of length L is $O(\frac{N}{L} \log_{Z} N)$, under the tall cache assumption that Z = Ω(L). This number of memory transfers has been shown to be asymptotically optimal for comparison sorts. Funnelsort also achieves the asymptotically optimal runtime complexity of Θ(NlogN).