Flashsort: Mechanism, Complexity Analysis & Interactive Visualizer

Flashsort

A brilliant, non-comparison sorting algorithm that achieves O(n) average-case speed in-place. It classifies elements into buckets, permutes them, and finishes with a fast Insertion Sort pass.

How it works

Flashsort, published by Karl-Dietrich Neubert in 1998, combines the speed of distribution sorting with the O(1) space efficiency of in-place algorithms. It operates in three distinct phases:

1. Classification: Divide the range of elements into $m$ classes. Size counts and prefix sums determine class boundaries.
2. Permutation: Relocate elements to their correct class boundaries using a permutation cycle. This step moves elements close to their final sorted positions without using an output array.
3. Straight Insertion Sort: The array is now highly ordered (elements in class $i$ are less than elements in class $i+1$). A final Insertion Sort pass resolves local ordering inside the classes in $O(n)$ total time.

Complexity

Interactive visualization

Pseudocode

procedure flashSort(A):
  n ← length(A)
  min, max ← findMinMax(A)
  m ← floor(0.43 * n)
  L ← array of size m initialized to 0
  
  for i from 0 to n - 1:
    classIdx ← floor(((m - 1) * (A[i] - min)) / (max - min))
    L[classIdx] ← L[classIdx] + 1
    
  L[0] ← L[0] - 1
  for i from 1 to m - 1:
    L[i] ← L[i] + L[i - 1]
    
  swap(A[maxIdx], A[0])
  
  numMoved ← 0
  j ← 0
  k ← m - 1
  while numMoved < n - 1:
    while j > L[k]:
      j ← j + 1
      k ← getClass(A[j])
    flash ← A[j]
    while j ≠ L[k] + 1:
      k ← getClass(flash)
      hold ← A[L[k]]
      A[L[k]] ← flash
      flash ← hold
      L[k] ← L[k] - 1
      numMoved ← numMoved + 1
      
  insertionSort(A)

JavaScript implementation

function flashSort(arr) {
  const n = arr.length;
  if (n <= 1) return arr;

  let min = arr[0];
  let max = arr[0];
  let maxIdx = 0;
  for (let i = 1; i < n; i++) {
    if (arr[i] < min) min = arr[i];
    if (arr[i] > max) {
      max = arr[i];
      maxIdx = i;
    }
  }

  if (min === max) return arr;

  const m = Math.max(2, Math.floor(0.43 * n));
  const L = new Array(m).fill(0);

  function getClass(x) {
    return Math.floor(((m - 1) * (x - min)) / (max - min));
  }

  for (let i = 0; i < n; i++) {
    const k = getClass(arr[i]);
    L[k]++;
  }

  L[0]--;
  for (let i = 1; i < m; i++) {
    L[i] = L[i] + L[i - 1];
  }

  let tmp = arr[maxIdx];
  arr[maxIdx] = arr[0];
  arr[0] = tmp;

  let numMoved = 0;
  let j = 0;
  let k = m - 1;

  while (numMoved < n - 1) {
    while (j > L[k]) {
      j++;
      k = getClass(arr[j]);
    }
    let flash = arr[j];
    while (j !== L[k] + 1) {
      k = getClass(flash);
      const hold = arr[L[k]];
      arr[L[k]] = flash;
      flash = hold;
      L[k]--;
      numMoved++;
    }
  }

  for (let i = 1; i < n; i++) {
    const key = arr[i];
    let j = i - 1;
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = key;
  }

  return arr;
}

Pros and cons

When to use it

• Uniformly Distributed Data: performs optimally when elements are distributed uniformly over the range.
• Tight Memory Constraints: ideal when speed must match bucket sorting but extra heap storage is limited.