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.
items on a machine with cache of size
This number of memory transfers has been shown to be asymptotically optimal for comparison sorts.
Funnelsort also achieves the asymptotically optimal runtime complexity of
Funnelsort operates on a contiguous array of
Merging is performed by a device called a k-merger, which is described in the section below.
The output of each input merger is connected to a buffer, a FIFO queue that can hold
The buffers are implemented as circular queues.
buffers are connected to the inputs of the output merger
In this construction, any input merger only outputs
items at once, but the buffer it outputs to has double the space.
elements, it recursively invokes its output merger
, 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
If this cannot be done (due to the merger running out of inputs), this step is skipped.
At the end of all these operations, the k-merger has output the first
of its input elements, in sorted order.
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
denote the space needed for a k-merger.
denote the number of cache misses incurred by a call to a k-merger, one can show that
For larger k, we can bound the number of times a
The total number of calls on input mergers is at most
In addition, the algorithm checks every buffer to see if needs to be filled.
Finally, the total cache misses
Lazy funnelsort is a modification of the funnelsort, introduced by Gerth Stølting Brodal and Rolf Fagerberg in 2002.
[3] 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.