American Flag Sort

American flag sort is an in place variant of radix sort. It distributes elements into buckets based on a digit, then permutes them into correct positions using cycle leader permutation. Unlike standard radix sort, it avoids auxiliary arrays.

This algorithm is commonly used for large datasets where memory allocation must be minimized.

Problem

Given an array $A$ of keys with digits in range $[0, b)$, reorder the array in place so that elements are sorted lexicographically.

Idea

1. Count how many elements fall into each bucket
2. Compute starting index of each bucket
3. Rearrange elements in place so that each element moves to its correct bucket
4. Recursively apply to each bucket for the next digit

The core technique is cycle leader permutation, which moves elements directly to their final bucket without extra storage.

Algorithm

american_flag_sort(A, lo, hi, d, base):
    if hi - lo <= 1:
        return

    count = [0] * base

    for i from lo to hi - 1:
        digit = get_digit(A[i], d)
        count[digit] += 1

    offset = [0] * base
    offset[0] = lo

    for i from 1 to base - 1:
        offset[i] = offset[i - 1] + count[i - 1]

    next = copy(offset)

    i = lo
    while i < hi:
        digit = get_digit(A[i], d)
        if i >= offset[digit] and i < offset[digit] + count[digit]:
            i += 1
        else:
            swap A[i] with A[next[digit]]
            next[digit] += 1

    for i from 0 to base - 1:
        start = offset[i]
        end = start + count[i]
        if end - start > 1:
            american_flag_sort(A, start, end, d + 1, base)

Example

Sort:

At the first digit level, elements are grouped by most significant digit into contiguous regions. Each region is then recursively sorted by the next digit.

Correctness

The counting phase determines exact bucket sizes. Offsets assign disjoint index intervals for each digit. The permutation phase moves each element into its correct interval. After placement, recursive sorting ensures order within each bucket.

Each element eventually reaches its correct position, and all buckets are independently sorted.

Complexity

Let:

• $n$ be number of elements
• $m$ be number of digits
• $b$ be base

Time:

Space:

This is more space efficient than standard radix sort, which requires $O(n)$ auxiliary memory.

Properties

When to Use

Use American flag sort when:

• memory allocation must be minimized
• keys are fixed width or digit accessible
• in place sorting is required
• performance close to radix sort is needed without extra buffers

Avoid when stability is required.

Implementation (Python)

def american_flag_sort(a, base=10):
    def sort(lo, hi, d):
        if hi - lo <= 1:
            return

        count = [0] * base

        for i in range(lo, hi):
            digit = get_digit(a[i], d)
            count[digit] += 1

        offset = [0] * base
        offset[0] = lo

        for i in range(1, base):
            offset[i] = offset[i - 1] + count[i - 1]

        next_pos = offset.copy()

        i = lo
        while i < hi:
            digit = get_digit(a[i], d)
            if offset[digit] <= i < offset[digit] + count[digit]:
                i += 1
            else:
                j = next_pos[digit]
                a[i], a[j] = a[j], a[i]
                next_pos[digit] += 1

        for i in range(base):
            start = offset[i]
            end = start + count[i]
            if end - start > 1:
                sort(start, end, d + 1)

    def get_digit(x, d):
        return (x // (10 ** d)) % 10

    sort(0, len(a), 0)
    return a