Funnelsort is a comparison-based sorting algorithm. It was introduced 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 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

edit

Basic Overview

edit

Funnelsort operates on a contiguous array of   elements. To sort the elements, it performs the following:

  1. Split the input into   arrays of size  , and sort the arrays recursively.
  2. Merge the   sorted sequences using a  -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.

k-mergers

edit

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 FIFO queue 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 (namely,   of them).

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 O, 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 (due to the merger running out of inputs), 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

edit

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

edit

The lazy funnelsort is a modification of the funnelsort, introduced by Brodal and Fagerberg. 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.

References

edit