Flashsort

Flashsort is a sorting algorithm with extremely good O(n) efficiency for balanced data sets, published in 1998 by Karl-Dietrich Neubert. 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 Ai, and is compu... more

Flashsort is a sorting algorithm with extremely good O(n) efficiency for balanced data sets, published in 1998 by Karl-Dietrich Neubert. 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 Ai, and is computed as 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 . For implementations of the algorithm, see . 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... less