Funnelsort

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 formula_1 items on a machine with cache of size formula_2 and cache lines of length formula_3 is formula_4, under the tall cache assumption that formula_5. This number of memory transfers has been shown to be asymptotically optimal for comparison sorts. Funnelsort also achieves the asymptotically optimal runtime complexity of formula_6.
Algorithm.
Basic overview.
Funnelsort operates on a contiguous array of formula_1 elements. To sort the elements, it performs the following:
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.
"k"-mergers.
A "k"-merger takes formula_12 sorted sequences. Upon one invocation of a k-merger, it outputs the first formula_13 elements of the sorted sequence obtained by merging the k input sequences.
At the top level, funnelsort uses a formula_8-merger on formula_8 sequences of length formula_9, and invokes this merger once.
The "k"-merger is built recursively out of formula_17-mergers. It consists of formula_17 input formula_17-mergers formula_20, and a single output formula_17-merger formula_22.
The "k" inputs are separated into formula_17 sets of formula_17 inputs each. Each of these sets is an input to one of the input mergers. The output of each input merger is connected to a buffer, a FIFO queue that can hold formula_25 elements. The buffers are implemented as circular queues.
The outputs of the formula_17 buffers are connected to the inputs of the output merger formula_22. Finally, the output of formula_22 is the output of the entire k-merger.
In this construction, any input merger only outputs formula_29 items at once, but the buffer it outputs to has double the space. This is done so that an input merger can be called only when its buffer does not have enough items, but that when it is called, it outputs a lot of items at once (namely, formula_29 of them).
A "k"-merger works recursively in the following way. To output formula_13 elements, it recursively invokes its output merger formula_29 times. However, before it makes a call to formula_22, it checks all of its buffers, filling each of them that are less than half full. To fill the i-th buffer, it recursively invokes the corresponding input merger formula_34 once. If this cannot be done (due to the merger running out of inputs), this step is skipped. Since this call outputs formula_29 elements, the buffer contains at least formula_29 elements. At the end of all these operations, the "k"-merger has output the first formula_13 of its input elements, in sorted order.
Analysis.
Most of the analysis of this algorithm revolves around analyzing the space and cache miss complexity of the k-merger.
The first important bound is that a k-merger can be fit in formula_38 space. To see this, we let formula_39 denote the space needed for a k-merger. To fit the formula_40 buffers of size formula_25 takes formula_38 space. To fit the formula_43 smaller buffers takes formula_44 space. Thus, the space satisfies the recurrence formula_45. This recurrence has solution formula_46.
It follows that there is a positive constant formula_47 such that a problem of size at most formula_48 fits entirely in cache, meaning that it incurs no additional cache misses.
Letting formula_49 denote the number of cache misses incurred by a call to a k-merger, one can show that formula_50 This is done by an induction argument. It has formula_51 as a base case. For larger k, we can bound the number of times a formula_17-merger is called. The output merger is called exactly formula_29 times. The total number of calls on input mergers is at most formula_54. This gives a total bound of formula_55 recursive calls. In addition, the algorithm checks every buffer to see if needs to be filled. This is done on formula_17 buffers every step for formula_29 steps, leading to a max of formula_58 cache misses for all the checks.
This leads to the recurrence formula_59, which can be shown to have the solution given above.
Finally, the total cache misses formula_60 for the entire sort can be analyzed. It satisfies the recurrence formula_61 This can be shown to have solution formula_62
Lazy funnelsort.
Lazy funnelsort is a modification of the funnelsort, introduced by Gerth Stølting Brodal and Rolf Fagerberg in 2002.
The modification is that when a merger is invoked, it does not have to fill each of its buffers. Instead, it lazily fills a buffer only when it is empty. This modification has the same asymptotic runtime and memory transfers as the original funnelsort, but has applications in cache-oblivious algorithms for problems in computational geometry in a method known as distribution sweeping.