Flashsort is adistribution sorting algorithm showinglinear computational complexityO(n) for uniformly distributed data sets and relatively little additional memory requirement. The original work was published in 1998 by Karl-Dietrich Neubert.[1]
Flashsort is an efficientin-place implementation ofhistogram sort, itself a type ofbucket sort. It assigns each of then input elements to one ofmbuckets, efficiently rearranges the input to place the buckets in the correct order, then sorts each bucket. The original algorithm sorts an input arrayA as follows:
Steps 1–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 (n/m elements each),[1] with the ideal being division intomquantiles. While the basic algorithm is a linearinterpolation sort, if the inputdistribution 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 efficientO(n) in-place algorithm for collecting the elements of each bucket together in the correct relative order using onlym words of additional memory.
The Flashsort rearrangement phase operates incycles. 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 finalO(n2) sorting.
To understand it with two variables per bucket, assume there are two arrays ofm additional words:Kb is the (fixed) upper limit of bucketb (andK0 = 0), whileLb is a (movable) index into bucketb, soKb−1 ≤Lb ≤Kb.
We maintain theloop invariant that each bucket is divided byLb into an unclassified prefix (Ai forKb−1 <i ≤Lb have yet to be moved to their target buckets) and a classified suffix (Ai forLb <i ≤Kb are all in the correct bucket and will not be moved again). InitiallyLb =Kb and all elements are unclassified. As sorting proceeds, theLb are decremented untilLb =Kb−1 for allb and all elements are classified into the correct bucket.
Each round begins by finding the first incompletely classified bucketc (which hasKc−1 <Lc) and taking the first unclassified element in that bucketAi wherei =Kc−1 + 1. (Neubert calls this the "cycle leader".) CopyAi to a temporary variablet and repeat:
When implemented with two variables per bucket in this way, the choice of each round's starting pointi 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 usesK to find the cycle leaders, it is in fact possible to do without it, allowing the entirem-word array to be eliminated. (After the distribution is complete, the bucket boundaries can be found inL.)
Suppose that we have classified all elements up toi−1, and are consideringAi as a potential new cycle leader. It is easy to compute its target bucketb. By the loop invariant, it is classified ifLb <i ≤Kb, and unclassified ifi is outside that range. The firstinequality is easy to test, but the second appears to require the valueKb.
It turns out that theinduction hypothesis that all elements up toi−1 are classified implies thati ≤Kb, so it is not necessary to test the second inequality.
Consider the bucketc which positioni falls into. That is,Kc−1 <i ≤Kc. By the induction hypothesis, all elements belowi, which includes all buckets up toKc−1 <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 thatb <c.
The only remaining case isb ≥c, which impliesKb ≥Kc ≥i,Q.E.D.
Incorporating this, the flashsort distribution algorithm begins withL as described above andi = 1. Then proceed:[1][2]
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 almost3n to at most2n + m − 1 by taking thelast unclassified element in an unfinished bucket as cycle leader:
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.
The only extra memory requirements are the auxiliary vectorL 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 adata 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 numberm of buckets is linear in the input sizen, each bucket has a constant size, so sorting a single bucket with anO(n2) algorithm like insertion sort has complexityO(12) =O(1). The running time of the final insertion sorts is thereforem ⋅ O(1) =O(m) =O(n).
Choosing a value form, the number of buckets, trades off time spent classifying elements (highm) and time spent in the final insertion sort step (lowm). For example, ifm is chosen proportional to√n, then the running time of the final insertion sorts is thereforem ⋅ O(√n2) =O(n3/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 toO(n2). Variations of the algorithm improve worst-case performance by using better-performing sorts such asquicksort or recursive flashsort on buckets which exceed a certain size limit.[2][3]
Form = 0.1n with uniformly distributed random data, flashsort is faster thanheapsort for alln and faster than quicksort forn > 80. It becomes about twice as fast as quicksort atn = 10000.[1] Note that these measurements were taken in the late 1990s, whenmemory hierarchies were much less dependent on cacheing.
Due to thein situ permutation that flashsort performs in its classification process, flashsort is notstable. 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 requireO(n) additional memory.