Flashsort

Flashsort is a sorting algorithm with extremely good $O(n)$ efficiency for balanced data sets published in 1998 by Karl-Dietrich Neubert.

Algorithm

Flashsort works based on the principle that in either a randomized or partially-ordered data set in which data are in a balanced distribution, one can immediately estimate where an item should be placed when one knows the range of the set. This approximate location is called the "class" of an item $A\_i$, and is computed as

$K(A\_i)\; =\; 1+\; extrm\{INT\}left((m-1)frac\{A\_i-A\_\; extrm\{min\{A\_\; extrm\{max\}-A\_\; extrm\{min\; ight)$

which gives a total of $m$ possible classes. After calculating the class of an element, it is inserted into the position in the array given by the order of the class (arranged from 1 through $m$). The final step is an insertion sort to arrange items in each class and fix any remaining errors [cite journal |last=Neubert |first=Karl-Dietrich |year=1998 |month=February |title=The Flashsort Algorithm |journal=Dr. Dobb's Journal |pages=123 |url=http://www.ddj.com/ |accessdate=2007-11-06] . For implementations of the algorithm, see [cite web |url=http://www.neubert.net/FSOIntro.html |title=The FlashSort Algorithm |accessdate=2007-11-06 |author=Karl-Dietrich Neubert |date=1998] .

Efficiency

In the ideal case of a balanced data set, the efficiency scales as $O(n)$ because each class is similarly sized, creating well-sorted data for the final insertion sort. As an in-place algorithm, it uses minimal memory and it also makes efficient use of the machine cache. In the worst case of unbalanced data, flashsort is as slow as insertion sort, scaling as $O(n^2)$ precisely due to the need to use insertion sort on data that was poorly sorted during classification. Using a faster algorithm such as quicksort in the final step alleviates this problem somewhat, giving an efficiency of $O(nlog\; n)$ for any randomized data, although the worst case is still $O(n^2)$ [cite web |url=http://jea.acm.org/ARTICLES/Vol5Nbr3/node4.html |title=Cache-Effective Quicksort |accessdate=2007-11-06 |author=Li Xiao, Xiaodong Zhang, Stefan A. Kubricht |work=Improving Memory Performance of Sorting Algorithms |publisher=Department of Computer Science, College of William and Mary, Williamsburg, VA 23187-8795] .

See also

* Big O notation
* Comparison sort
* Computational complexity theory
* List of algorithms

References

External links

* [http://elliottback.com/wp/archives/2006/01/07/sorting-in-linear-time/ Sorting in Linear time]
* [http://citeseer.ist.psu.edu/91922.html Implementations of Randomized Sorting on Large Parallel Machines (1992)]
* [http://stinet.dtic.mil/oai/oai?verb=getRecord&metadataPrefix=html&identifier=ADA253638 Implementation of Parallel Algorithms (1992)]