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

Introduction

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.

Classification
Accumulation

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.

• Karl-Dietrich Neubert The FlashSort Algorithm
  This is an MS 6.0 Word document as published in the Proceedings of the
  euroFORTH'97 -Conference, Oxford, England,Sept.26-28 1997
  
  
• Karl-Dietrich Neubert, FlashSort1 Algorithm in
  Dr. Dobb's Journal Feb.1998,p.123
  CLICK HERE TO SUBSCRIBE TO DDJ
  A collection of
  FlashSort demos

  For animations of the FlashSort principle and runtime, select
  Collection of FlashSort demos
  A collection of
  FlashSort codes

  For codes in various languages and various modifications of the FlashSort algorithm see
  Collection of FlashSort codes.
  

Back

To go back to the Welcome page click here.