Flashsort

{{short description|O(n) sorting algorithm}} '''Flashsort''' is a distribution sorting algorithm showing linear computational complexity {{mvar|''O''(''n'')}} for uniformly distributed data sets and relatively little additional memory requirement. The original work was published in 1998 by Karl-Dietrich Neubert.<ref name="neubert_journal">{{cite journal |last=Neubert |first=Karl-Dietrich |date=February 1998 |title=The Flashsort1 Algorithm |journal=Dr. Dobb's Journal |volume=23 |issue=2 |pages=123–125, 131 |url=http://www.ddj.com/architect/184410496 |access-date=2007-11-06}}</ref>

== Concept == Flashsort is an efficient in-place implementation of histogram sort, itself a type of bucket sort. It assigns each of the {{mvar|n}} input elements to one of {{mvar|m}} ''buckets'', efficiently rearranges the input to place the buckets in the correct order, then sorts each bucket. The original algorithm sorts an input array {{mvar|A}} as follows: # Using a first pass over the input or ''a priori'' knowledge, find the minimum and maximum sort keys. # Linearly divide the range {{math|[''A''_min, ''A''_max]}} into {{mvar|m}} buckets. # Make one pass over the input, counting the number of elements {{mvar|A_i}} which fall into each bucket. (Neubert calls the buckets "classes" and the assignment of elements to their buckets "classification".) # Convert the counts of elements in each bucket to a prefix sum, where {{mvar|L_b}} is the number of elements {{mvar|A_i}} in bucket {{mvar|b}} or less. ({{math|1=''L''₀ = 0}} and {{math|1=''L_m'' = ''n''}}.) # Rearrange the input so all elements of each bucket {{mvar|b}} are stored in positions {{mvar|A_i}} where {{math|''L''_{''b''&minus;1} &lt; ''i'' ≤ ''L_b''}}. # Sort each bucket using insertion sort.

Steps 1&ndash;3 and 6 are common to any bucket sort, and can be improved using techniques generic to bucket sorts. In particular, the goal is for the buckets to be of approximately equal size ({{math|''n''/''m''}} elements each),<ref name="neubert_journal" /> with the ideal being division into {{mvar|m}} quantiles. While the basic algorithm is a linear interpolation sort, if the input distribution is known to be non-uniform, a non-linear division will more closely approximate this ideal. Likewise, the final sort can use any of a number of techniques, including a recursive flash sort.

What distinguishes flash sort is step 5: an efficient {{math|''O''(''n'')}} in-place algorithm for collecting the elements of each bucket together in the correct relative order using only {{mvar|m}} words of additional memory.

== Memory efficient implementation == The Flashsort rearrangement phase operates in cycles. Elements start out "unclassified", then are moved to the correct bucket and considered "classified". The basic procedure is to choose an unclassified element, find its correct bucket, exchange it with an unclassified element there (which must exist, because we counted the size of each bucket ahead of time), mark it as classified, and then repeat with the just-exchanged unclassified element. Eventually, the element is exchanged with itself and the cycle ends.

The details are easy to understand using two (word-sized) variables per bucket. The clever part is the elimination of one of those variables, allowing twice as many buckets to be used and therefore half as much time spent on the final {{math|''O''(''n''²)}} sorting.

To understand it with two variables per bucket, assume there are two arrays of {{mvar|m}} additional words: {{mvar|K_b}} is the (fixed) upper limit of bucket {{mvar|b}} (and {{math|1=''K''₀ = 0}}), while {{mvar|L_b}} is a (movable) index into bucket {{mvar|b}}, so {{math|''K''_{''b''&minus;1} ≤ ''L_b'' ≤ ''K_b''}}.

We maintain the loop invariant that each bucket is divided by {{mvar|L_b}} into an unclassified prefix ({{mvar|A_i}} for {{math|''K''_{''b''&minus;1} &lt; ''i'' ≤ ''L_b''}} have yet to be moved to their target buckets) and a classified suffix ({{mvar|A_i}} for {{math|''L_b'' &lt; ''i'' ≤ ''K_b''}} are all in the correct bucket and will not be moved again). Initially {{math|1=''L_b'' = ''K_b''}} and all elements are unclassified. As sorting proceeds, the {{mvar|L_b}} are decremented until {{math|1=''L_b'' = ''K''_{''b''&minus;1}}} for all {{mvar|b}} and all elements are classified into the correct bucket.

Each round begins by finding the first incompletely classified bucket {{mvar|c}} (which has {{math|''K''_{''c''&minus;1} &lt; ''L_c''}}) and taking the first unclassified element in that bucket {{mvar|A_i}} where {{math|1=''i'' = ''K''_{''c''&minus;1} + 1}}. (Neubert calls this the "cycle leader".) Copy {{mvar|A_i}} to a temporary variable {{mvar|t}} and repeat: * Compute the bucket {{mvar|b}} to which {{mvar|t}} belongs. * Let {{math|1=''j'' = ''L_b''}} be the location where {{mvar|t}} will be stored. * Exchange {{mvar|t}} with {{mvar|A_j}}, i.e. store {{mvar|t}} in {{mvar|A_j}} while fetching the previous value {{mvar|A_j}} thereby displaced. * Decrement {{mvar|L_b}} to reflect the fact that {{mvar|A_j}} is now correctly classified. * If {{math|''j'' ≠ ''i''}}, restart this loop with the new {{mvar|t}}. * If {{math|1=''j'' = ''i''}}, this round is over and find a new first unclassified element {{mvar|A_i}}. * When there are no more unclassified elements, the distribution into buckets is complete.

When implemented with two variables per bucket in this way, the choice of each round's starting point {{mvar|i}} is in fact arbitrary; ''any'' unclassified element may be used as a cycle leader. The only requirement is that the cycle leaders can be found efficiently.

Although the preceding description uses {{mvar|K}} to find the cycle leaders, it is in fact possible to do without it, allowing the entire {{mvar|m}}-word array to be eliminated. (After the distribution is complete, the bucket boundaries can be found in {{mvar|L}}.)

Suppose that we have classified all elements up to {{math|''i''&minus;1}}, and are considering {{mvar|A_i}} as a potential new cycle leader. It is easy to compute its target bucket {{mvar|b}}. By the loop invariant, it is classified if {{math|''L_b'' &lt; ''i'' ≤ ''K_b''}}, and unclassified if {{mvar|i}} is outside that range. The first inequality is easy to test, but the second appears to require the value {{mvar|K_b}}.

It turns out that the induction hypothesis that all elements up to {{math|''i''&minus;1}} are classified implies that {{math|''i'' ≤ ''K_b''}}, so it is not necessary to test the second inequality.

Consider the bucket {{mvar|c}} which position {{mvar|i}} falls into. That is, {{math|''K''_{''c''&minus;1} &lt; ''i'' ≤ ''K_c''}}. By the induction hypothesis, all elements below {{mvar|i}}, which includes all buckets up to {{math|''K''_{''c''&minus;1} &lt; ''i''}}, are completely classified. I.e. no elements which belong in those buckets remain in the rest of the array. Therefore, it is not possible that {{math|''b'' &lt; ''c''}}.

The only remaining case is {{math|''b'' ≥ ''c''}}, which implies {{math|''K_b'' ≥ ''K_c'' ≥ ''i''}}, Q.E.D.

Incorporating this, the flashsort distribution algorithm begins with {{mvar|L}} as described above and {{math|1=''i'' = 1}}. Then proceed:<ref name="neubert_journal" /><ref name="neubert_code">{{cite web |url=http://www.neubert.net/FSOIntro.html |title=The FlashSort Algorithm |access-date=2007-11-06 |last=Neubert |first=Karl-Dietrich |year=1998}}</ref> * If {{math|''i'' &gt; ''n''}}, the distribution is complete. * Given {{mvar|A_i}}, compute the bucket {{mvar|b}} to which it belongs. * If {{math|''i'' ≤ ''L_b''}}, then {{mvar|A_i}} is unclassified. Copy it a temporary variable {{mvar|t}} and: ** Let {{math|1=''j'' = ''L_b''}} be the location where {{mvar|t}} will be stored. ** Exchange {{mvar|t}} with {{mvar|A_j}}, i.e. store {{mvar|t}} in {{mvar|A_j}} while fetching the previous value {{mvar|A_j}} thereby displaced. ** Decrement {{mvar|L_b}} to reflect the fact that {{mvar|A_j}} is now correctly classified. ** If {{math|''j'' ≠ ''i''}}, compute the bucket {{mvar|b}} to which {{mvar|t}} belongs and restart this (inner) loop with the new {{mvar|t}}. * {{mvar|A_i}} is now correctly classified. Increment {{mvar|i}} and restart the (outer) loop.

While saving memory, Flashsort has the disadvantage that it recomputes the bucket for many already-classified elements. This is already done twice per element (once during the bucket-counting phase and a second time when moving each element), but searching for the first unclassified element requires a third computation for most elements. This could be expensive if buckets are assigned using a more complex formula than simple linear interpolation. A variant reduces the number of computations from almost {{math|3''n''}} to at most {{math|2''n''&nbsp;+&nbsp;''m''&nbsp;&minus;&nbsp;1}} by taking the ''last'' unclassified element in an unfinished bucket as cycle leader: * Maintain a variable {{mvar|c}} identifying the first incompletely-classified bucket. Let {{math|1=''c'' = 1}} to begin with, and when {{mvar|''c'' &gt; ''m''}}, the distribution is complete. * Let {{math|1=''i'' = ''L_c''}}. If {{math|1=''i'' = ''L''_{''c''&minus;1}}}, increment {{mvar|c}} and restart this loop. ({{math|1=''L''₀ = 0}}.) * Compute the bucket {{mvar|b}} to which {{mvar|A_i}} belongs. * If {{math|''b'' &lt; ''c''}}, then {{math|1=''L_c'' = ''K''_{''c''&minus;1}}} and we are done with bucket {{mvar|c}}. Increment {{mvar|c}} and restart this loop. * If {{math|1=''b'' = ''c''}}, the classification is trivial. Decrement {{mvar|L_c}} and restart this loop. * If {{math|''b'' &gt; ''c''}}, then {{mvar|A_i}} is unclassified. Perform the same classification loop as the previous case, then restart this loop.

Most elements have their buckets computed only twice, except for the final element in each bucket, which is used to detect the completion of the following bucket. A small further reduction can be achieved by maintaining a count of unclassified elements and stopping when it reaches zero.

== Performance == The only extra memory requirements are the auxiliary vector {{mvar|L}} for storing bucket bounds and the constant number of other variables used. Further, each element is moved (via a temporary buffer, so two move operations) only once. However, this memory efficiency comes with the disadvantage that the array is accessed randomly, so cannot take advantage of a data cache smaller than the whole array.

As with all bucket sorts, performance depends critically on the balance of the buckets. In the ideal case of a balanced data set, each bucket will be approximately the same size. If the number {{mvar|m}} of buckets is linear in the input size {{mvar|n}}, each bucket has a constant size, so sorting a single bucket with an {{math|''O''(''n''²)}} algorithm like insertion sort has complexity {{math|1=''O''(1²) = ''O''(1)}}. The running time of the final insertion sorts is therefore {{math|1=''m'' ⋅ O(1) = ''O''(''m'') = ''O''(''n'')}}.

Choosing a value for {{mvar|m}}, the number of buckets, trades off time spent classifying elements (high {{mvar|m}}) and time spent in the final insertion sort step (low {{mvar|m}}). For example, if {{mvar|m}} is chosen proportional to {{math|{{sqrt|''n''}}}}, then the running time of the final insertion sorts is therefore {{math|1=''m'' ⋅ O({{math|{{sqrt|''n''}}²}}) = ''O''(''n''^3/2)}}.

In the worst-case scenarios where almost all the elements are in a few buckets, the complexity of the algorithm is limited by the performance of the final bucket-sorting method, so degrades to {{math|''O''(''n''²)}}. Variations of the algorithm improve worst-case performance by using better-performing sorts such as quicksort or recursive flashsort on buckets which exceed a certain size limit.<ref name="neubert_code" /><ref>{{cite journal |first1=Li |last1=Xiao |first2=Xiaodong |last2=Zhang |first3=Stefan A. |last3=Kubricht |title=Improving Memory Performance of Sorting Algorithms: Cache-Effective Quicksort |journal=ACM Journal of Experimental Algorithmics |volume=5 |year=2000<!--ACM page says "December" for all articles published 2000, so not sure if it's true--> |doi=10.1145/351827.384245 |citeseerx=10.1.1.43.736<!--Also 10.1.1.474.5688--> |url=http://jea.acm.org/ARTICLES/Vol5Nbr3/node4.html |access-date=2007-11-06 |archive-url=https://web.archive.org/web/20071102070431/http://jea.acm.org/ARTICLES/Vol5Nbr3/node4.html |archive-date=2007-11-02 |url-status=dead }}</ref>

For {{math|1=''m'' = 0.1 ''n''}} with uniformly distributed random data, flashsort is faster than heapsort for all {{mvar|n}} and faster than quicksort for {{math|''n'' > 80}}. It becomes about twice as fast as quicksort at {{math|1=''n'' = 10000}}.<ref name="neubert_journal" /> Note that these measurements were taken in the late 1990s, when memory hierarchies were much less dependent on cacheing.<!--As can be seen by benchmarks maxing out at n=10000, which is "fits into L1 cache" these days.-->

Due to the ''in situ'' permutation that flashsort performs in its classification process, flashsort is not stable. If stability is required, it is possible to use a second array so elements can be classified sequentially. However, in this case, the algorithm will require {{math|''O''(''n'')}} additional memory.

== See also == * Interpolation search, using the distribution of items for searching rather than sorting

== References == {{reflist}}

== External links == * [https://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.294.8609 Implementations of Randomized Sorting on Large Parallel Machines (1992)] * [https://archive.org/details/DTIC_ADA253638 Implementation of Parallel Algorithms (1992)] * [http://home.westman.wave.ca/~rhenry/sort/#flashsort Visualization of Flashsort] {{Webarchive|url=https://web.archive.org/web/20110705025510/http://home.westman.wave.ca/~rhenry/sort/#flashsort |date=2011-07-05 }}

{{sorting}}

Category:Sorting algorithms