In the external memory model, the number of memory transfers it needs to perform a sort of items on a machine with cache of size and cache lines of length is, under the tall cache assumption that. This number of memory transfers has been shown to be asymptotically optimal for comparison sorts. Funnelsort also achieves the asymptotically optimal runtime complexity of.
Algorithm
Basic overview
Funnelsort operates on a contiguous array of elements. To sort the elements, it performs the following:
Split the input into arrays of size, and sort the arrays recursively.
Merge the sorted sequences using a -merger.
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 sorted sequences. Upon one invocation of a k-merger, it outputs the first elements of the sorted sequence obtained by merging the k input sequences. At the top level, funnelsort uses a -merger on sequences of length, and invokes this merger once. The k-merger is built recursively out of -mergers. It consists of input -mergers, and a single output -merger. The k inputs are separated into sets of 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 FIFOqueue that can hold elements. The buffers are implemented as circular queues. The outputs of the buffers are connected to the inputs of the output merger. Finally, the output of is the output of the entire k-merger. In this construction, any input merger only outputs 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. A k-merger works recursively in the following way. To output elements, it recursively invokes its output merger times. However, before it makes a call to, 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 once. If this cannot be done, this step is skipped. Since this call outputs elements, the buffer contains at least elements. At the end of all these operations, the k-merger has output the first 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 space. To see this, we let denote the space needed for a k-merger. To fit the buffers of size takes space. To fit the smaller buffers takes space. Thus, the space satisfies the recurrence. This recurrence has solution. It follows that there is a positive constant such that a problem of size at most fits entirely in cache, meaning that it incurs no additional cache misses. Letting denote the number of cache misses incurred by a call to a k-merger, one can show that This is done by an induction argument. It has as a base case. For larger k, we can bound the number of times a -merger is called. The output merger is called exactly times. The total number of calls on input mergers is at most. This gives a total bound of recursive calls. In addition, the algorithm checks every buffer to see if needs to be filled. This is done on buffers every step for steps, leading to a max of cache misses for all the checks. This leads to the recurrence, which can be shown to have the solution given above. Finally, the total cache misses for the entire sort can be analyzed. It satisfies the recurrence This can be shown to have solution
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.
