Funnelsort

Summary

(Learn how and when to remove this template message)

We 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.[1][2]

Mathematical propertiesEdit

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  .

AlgorithmEdit

Basic overviewEdit

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-mergersEdit

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  , 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.

AnalysisEdit

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 funnelsortEdit

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.

See alsoEdit

ReferencesEdit

  1. ^ M. Frigo, C.E. Leiserson, H. Prokop, and S. Ramachandran. Cache-oblivious algorithms. In Proceedings of the 40th IEEE Symposium on Foundations of Computer Science (FOCS 99), pp. 285-297. 1999. Extended abstract at IEEE, at Citeseer.
  2. ^ Harald Prokop. Cache-Oblivious Algorithms. Masters thesis, MIT. 1999.
  3. ^ Brodal, Gerth Stølting; Fagerberg, Rolf (25 June 2002). "Cache Oblivious Distribution Sweeping". Automata, Languages and Programming. Lecture Notes in Computer Science. Vol. 2380. Springer. pp. 426–438. CiteSeerX 10.1.1.117.6837. doi:10.1007/3-540-45465-9_37. ISBN 978-3-540-43864-9.. See also the longer technical report.