Funnelsort is a comparison-based sorting algorithm. It is similar to mergesort, but it is a cache-oblivious algorithm, designed for a setting where the number of elements to sort is too large to fit in a cache where operations are done. It was introduced by Matteo Frigo, Charles Leiserson, Harald Prokop, and Sridhar Ramachandran in 1999 in the context of the cache oblivious model.
Mathematical properties In the external memory model, the number of memory transfers it needs to perform a sort of N {\displaystyle N} items on a machine with cache of size Z {\displaystyle Z} and cache lines of length L {\displaystyle L} is O ( N L log Z N ) {\displaystyle O\left({\tfrac {N}{L}}\log _{Z}N\right)} , under the tall cache assumption that Z = Ω ( L 2 ) {\displaystyle Z=\Omega (L^{2})} . This number of memory transfers has been shown to be asymptotically optimal for comparison sorts. Funnelsort also achieves the asymptotically optimal runtime complexity of Θ ( N log N ) {\displaystyle \Theta (N\log N)} .
Algorithm
Basic overview Funnelsort operates on a contiguous array of N {\displaystyle N} elements. To sort the elements, it performs the following:
Split the input into N 1 / 3 {\displaystyle N^{1/3}} arrays of size N 2 / 3 {\displaystyle N^{2/3}} , and sort the arrays recursively. Merge the N 1 / 3 {\displaystyle N^{1/3}} sorted sequences using a N 1 / 3 {\displaystyle N^{1/3}} -merger. (This process will be described in more detail.) Funnelsort is similar to merge sort in that some number of subarrays are recursively sorted, after which a merging step combines the subarrays into one sorted array. Merging is performed by a device called a k-merger, which is described in the section below.
… excerpt ends here. Continue reading the full article.
