www.neubert.net - Dr. Neubert's Website
The Entropy Reduction Laboratory

The FlashSort Algorithm

The Problem
of in-situ sorting with
minimal auxiliary space
in minimal time.


In "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 in-situ permutation is inherently connected with the problem of finding the cycle leaders, and in-situ 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 in-situ 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 in-situ 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.


run the loops:
- find cycle leader
- in situ permutation

short range sorting

The FlashSort Algorithm

FlashSort sorts n elements in O(n) time. Flash-Sort 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 with L(k(A(i))) >= i. Evidently, in addition to the array A of length n which holds the n elements to be sorted, the only auxiliary vector is the L(k)-vector. The size of this vector is equal to the number m of classes which is small compared to n, e.g. m typically may be set to m=0.1 n in case of floating point numbers.
Finally,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
A collection of
FlashSort codes
    To go back to the Welcome page click here.

This page and each part of it Copyright © 1998 Karl-Dietrich Neubert.
All Rights Reserved
Design by Vladimir Marek.
Last update of the page: March 18, 2003