

The Problem of insitu sorting with minimal auxiliary space in minimal time. 
IntroductionIn "Mathematical Analysis of Algorithms", (Information Processing '71, North Holland Publ.'72) Donald Knuth remarked "... that research on computional complexity is an interesting way to sharpen our tools for more routine problems we face from day to day."With respect to the sorting problem, Knuth points out, that time effective insitu permutation is inherently connected with the problem of finding the cycle leaders, and insitu permutations could easily be performed in O(n) time if we would be allowed to manipulate n extra "tag" bits specifying how much of the permutation has been carried out at any time. Without such tag bits, he concludes "it seems reasonable to conjecture that every algorithm will require for insitu permutation at least n log n steps on the average". Now this conjecture is shown not to be valid. A new efficient way to find cycle leaders is presented and insitu permutations can be performed in optimal time. The algorithm FlashSort sorts in O(n) time without the manipulation of n extra "tag" bits. Here an auxiliary vector of only length m is required, where m is a small fraction of the number of elements n. 
Classification Accumulation run the loops:  find cycle leader  in situ permutation short range sorting 
The FlashSort AlgorithmFlashSort sorts n elements in O(n) time. FlashSort uses a vector L(k) of length m in a first step for the classification of the elements of array A. Then, in a second step, the resulting counts are accumulated and the L(k) point to the class boundaries. Then the elements are sorted by in situ permutation. During the permutation, the L(k) are decremented by a unit step at each new placement of an element of class k in the array A. A crucial aspect of FlashSort is that for identifying new cycle leaders. A cycle ends, if the the vector L(k) points to the position of an element below the classboundary of class k. The new cycle leader is the element situated in the lowest position complying to the complimentary condition, i.e. for which L(k) points to a position withFinally,a small number of partially distinguishable elements are sorted locally within their classes either by recursion or by a simple conventional sort algorithm. 
In these papers you find a more detailed description of the algorithm. 

A collection of FlashSort demos 
Collection of FlashSort demos 
A collection of FlashSort codes 
Collection of FlashSort codes. 
Back 
