American Flag Sort: Mechanism, Complexity Analysis & Interactive Visualizer

American Flag Sort

An efficient, in-place variant of MSD Radix Sort. It classifies elements into buckets and uses a permutation cycle to swap them into class boundaries in-place.

How it works

Standard Radix Sort requires an auxiliary array to copy elements back and forth. American Flag Sort avoids this overhead by using a smart in-place permutation cycle, similar to Flashsort, but applied to digit-based radix boundaries.

1. Count the frequency of each digit (0-9) at the current digit position (starting from the MSD).
2. Compute the starting and ending index offsets (boundaries) for each bucket in the array.
3. Use a permutation cycle to swap elements into their correct bucket boundaries in-place, advancing the bucket pointers as elements are placed.
4. Recursively sort each bucket for the next significant digit position until the entire array is sorted.

Complexity

Interactive visualization

Pseudocode

procedure americanFlagSort(A):
  n ← length(A)
  min, max ← findMinMax(A)
  maxExp ← highestPowerOf10(max)
  americanSort(A, 0, n - 1, maxExp)

procedure americanSort(A, lo, hi, exp):
  if lo >= hi or exp <= 0: return
  
  count ← array of size 10 initialized to 0
  start ← array of size 10 initialized to 0
  end ← array of size 10 initialized to 0
  
  for i from lo to hi:
    digit ← (A[i] / exp) % 10
    count[digit] ← count[digit] + 1
    
  start[0] ← lo
  end[0] ← lo + count[0]
  for i from 1 to 9:
    start[i] ← end[i - 1]
    end[i] ← start[i] + count[i]
    
  for i from 0 to 9:
    while start[i] < end[i]:
      val ← A[start[i]]
      digit ← (val / exp) % 10
      if digit = i:
        start[i] ← start[i] + 1
      else:
        targetIdx ← start[digit]
        swap(A[start[i]], A[targetIdx])
        start[digit] ← start[digit] + 1
        
  currentStart ← lo
  for i from 0 to 9:
    size ← count[i]
    if size > 1:
      americanSort(A, currentStart, currentStart + size - 1, exp / 10)
    currentStart ← currentStart + size

JavaScript implementation

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

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

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

  let maxExp = 1;
  while (Math.floor(max / maxExp) >= 10) {
    maxExp *= 10;
  }

  const RADIX = 10;

  function sort(lo, hi, exp) {
    if (lo >= hi || exp <= 0) return;

    const count = new Array(RADIX).fill(0);
    const start = new Array(RADIX).fill(0);
    const end = new Array(RADIX).fill(0);

    for (let i = lo; i <= hi; i++) {
      const digit = Math.floor(arr[i] / exp) % RADIX;
      count[digit]++;
    }

    start[0] = lo;
    end[0] = lo + count[0];
    for (let i = 1; i < RADIX; i++) {
      start[i] = end[i - 1];
      end[i] = start[i] + count[i];
    }

    for (let i = 0; i < RADIX; i++) {
      while (start[i] < end[i]) {
        const val = arr[start[i]];
        const digit = Math.floor(val / exp) % RADIX;
        if (digit === i) {
          start[i]++;
        } else {
          const targetIdx = start[digit];
          arr[start[i]] = arr[targetIdx];
          arr[targetIdx] = val;
          start[digit]++;
        }
      }
    }

    let currentStart = lo;
    for (let i = 0; i < RADIX; i++) {
      const size = count[i];
      if (size > 1) {
        sort(currentStart, currentStart + size - 1, Math.floor(exp / RADIX));
      }
      currentStart += size;
    }
  }

  sort(0, n - 1, maxExp);

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

  return arr;
}

Pros and cons

When to use it

• In-Place Lexicographical Sorting: ideal for sorting large arrays of strings or prefix codes without allocating auxiliary memory.
• Embedded Systems: highly suited for environments where memory space is extremely constrained.