Linear Time Sorts

March 2026 · 28 min read

Comparison-based sorting has a proven lower bound of $\Omega(n \log n)$. But what if we do not compare elements at all? By exploiting the structure of the data (integer keys, bounded range, digit decomposition), we can sort in linear time. This post covers the three main non-comparison sorts: counting sort, radix sort, and bucket sort.

The catch: these algorithms have constraints. They work only on specific types of input (usually non-negative integers within a known range). But when those constraints are met, they are dramatically faster than any comparison-based sort.

Counting Sort

Counting sort works by counting how many times each value appears, then using those counts to place elements directly into their correct positions. It does not compare any two elements.

How It Works

Step-Through Animation

C++ Implementation

void countingSort(vector<int>& arr) {
    if (arr.empty()) return;
    int maxVal = *max_element(arr.begin(), arr.end());
    vector<int> count(maxVal + 1, 0);

    // Step 1: count occurrences
    for (int x : arr) count[x]++;

    // Step 2: prefix sums
    for (int i = 1; i <= maxVal; i++)
        count[i] += count[i - 1];

    // Step 3: build output (right to left for stability)
    vector<int> output(arr.size());
    for (int i = arr.size() - 1; i >= 0; i--) {
        output[count[arr[i]] - 1] = arr[i];
        count[arr[i]]--;
    }
    arr = output;
}

Analysis

• Time: $O(n + k)$, where $n$ is the number of elements and $k$ is the range of values.
• Space: $O(n + k)$ for the count array and output array.
• Stable: Yes, when we scan from right to left in step 3.

Example: sorting exam scores (0 to 100) for a class of 500 students. Here $k = 100$ and $n = 500$, so counting sort runs in $O(600)$. Merge sort would take $O(500 \cdot 9) \approx 4500$ comparisons.

Radix Sort

Radix sort handles the problem of large ranges by sorting one digit at a time. Instead of counting all possible values, it sorts by the least significant digit, then the next, and so on. Each digit sort uses counting sort as a subroutine.

How It Works

1. Find the maximum number of digits $d$ in the input.
2. For each digit position from least significant to most significant:
3. Use a stable sort (counting sort with $k = 9$) on that digit.

Sorting from least significant to most significant works because each stable sort preserves the relative order from previous digit sorts. After processing the most significant digit, the entire array is sorted.

Radix Sort Visualization

C++ Implementation

void countingSortByDigit(vector<int>& arr, int exp) {
    int n = arr.size();
    vector<int> output(n);
    int count[10] = {0};

    for (int i = 0; i < n; i++)
        count[(arr[i] / exp) % 10]++;

    for (int i = 1; i < 10; i++)
        count[i] += count[i - 1];

    for (int i = n - 1; i >= 0; i--) {
        int digit = (arr[i] / exp) % 10;
        output[count[digit] - 1] = arr[i];
        count[digit]--;
    }
    arr = output;
}

void radixSort(vector<int>& arr) {
    if (arr.empty()) return;
    int maxVal = *max_element(arr.begin(), arr.end());
    for (int exp = 1; maxVal / exp > 0; exp *= 10)
        countingSortByDigit(arr, exp);
}

Analysis

• Time: $O(d \cdot (n + k))$, where $d$ is the number of digits and $k$ is the base (10 for decimal). If we use base $n$, then $d = \log_n(\text{max})$ and $k = n$, giving $O(n \cdot \log_n(\text{max}))$.
• Space: $O(n + k)$ for the counting sort auxiliary arrays.
• Stable: Yes, because counting sort (the subroutine) is stable.

Choosing the Base

The base does not have to be 10. Using base 256, each 32-bit integer has only 4 "digits" (bytes). This means 4 passes of counting sort over a count array of size 256. In practice, base-256 radix sort is extremely fast for sorting arrays of 32-bit integers.

// Base-256 radix sort for 32-bit unsigned integers
void radixSort256(vector<uint32_t>& arr) {
    int n = arr.size();
    vector<uint32_t> buf(n);
    for (int shift = 0; shift < 32; shift += 8) {
        int count[256] = {0};
        for (int i = 0; i < n; i++)
            count[(arr[i] >> shift) & 0xFF]++;
        for (int i = 1; i < 256; i++)
            count[i] += count[i - 1];
        for (int i = n - 1; i >= 0; i--)
            buf[--count[(arr[i] >> shift) & 0xFF]] = arr[i];
        swap(arr, buf);
    }
}

Bucket Sort

Bucket sort distributes elements into a fixed number of buckets, sorts each bucket individually (typically with insertion sort), and then concatenates all buckets. It works best when the input is uniformly distributed over a known range.

How It Works

1. Create $k$ empty buckets.
2. Distribute each element into a bucket based on its value: bucket index $= \lfloor k \cdot \text{arr}[i] / (\text{max} + 1) \rfloor$.
3. Sort each bucket (using insertion sort or any sort).
4. Concatenate all buckets in order.

Bucket Sort Visualization

C++ Implementation

void bucketSort(vector<float>& arr) {
    int n = arr.size();
    if (n <= 1) return;
    vector<vector<float>> buckets(n);

    for (float x : arr) {
        int idx = (int)(n * x);  // assumes x in [0, 1)
        buckets[idx].push_back(x);
    }

    for (auto& b : buckets)
        sort(b.begin(), b.end());  // insertion sort for small buckets

    int pos = 0;
    for (auto& b : buckets)
        for (float x : b)
            arr[pos++] = x;
}

Analysis

• Best/Average time: $O(n + k)$ when elements are uniformly distributed. Each bucket gets $O(1)$ elements on average, so sorting buckets is $O(1)$ per bucket.
• Worst time: $O(n^2)$ when all elements fall into the same bucket (degenerates to the inner sort).
• Space: $O(n + k)$ for the buckets.
• Stable: Yes, if the inner sort is stable.

When to Use Which

Decision Guide

• Values are integers 0 to $k$ and $k = O(n)$? Use counting sort.
• Values are integers with $d$ digits and $d$ is small? Use radix sort.
• Values are uniformly distributed floats in a known range? Use bucket sort.
• None of the above? Fall back to a comparison sort (merge sort or quicksort).

Handling Negative Numbers

Counting sort and radix sort assume non-negative keys. To handle negatives:

// Approach 1: Shift all values to non-negative
void countingSortWithNegatives(vector<int>& arr) {
    int minVal = *min_element(arr.begin(), arr.end());
    for (int& x : arr) x -= minVal;  // shift to [0, max-min]
    countingSort(arr);
    for (int& x : arr) x += minVal;  // shift back
}

// Approach 2: Separate negatives and positives
void radixSortSigned(vector<int>& arr) {
    vector<int> neg, pos;
    for (int x : arr) {
        if (x < 0) neg.push_back(-x);
        else pos.push_back(x);
    }
    radixSort(neg);
    radixSort(pos);
    reverse(neg.begin(), neg.end());
    int i = 0;
    for (int x : neg) arr[i++] = -x;
    for (int x : pos) arr[i++] = x;
}

Practice Problems

• Sort Colors (LeetCode 75): Counting sort with $k = 2$. Three-way partition also works.
• Maximum Gap (LeetCode 164): Radix sort, then find the max consecutive difference.
• Top K Frequent Elements (LeetCode 347): Count frequencies, then bucket sort by frequency.
• Sort an Array (LeetCode 912): Any sort works. Radix sort gives the fastest submission for random integer inputs.
• H-Index (LeetCode 274): Counting sort with $k = n$.

Summary

• Non-comparison sorts break the $\Omega(n \log n)$ barrier by exploiting data structure (integer keys, bounded range).
• Counting sort counts occurrences and uses prefix sums. Best when range $k$ is close to $n$.
• Radix sort processes digits one at a time using a stable subroutine (counting sort). Best for fixed-width keys.
• Bucket sort distributes into bins and sorts each bin. Best for uniformly distributed data.
• All three are stable (when implemented correctly) and use $O(n + k)$ space.
• The tradeoff: faster time, but restricted input types and higher memory usage.