SyntaxPilot
Courses/DSA and Coding Problems/Lesson 19
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

DSA and Coding Problems · Lesson 19 of 90

Counting sort, radix sort and the Dutch national flag

queued

These are the notes for DSA episode 19, the last episode of the sorting block. Merge sort and quick sort reach O(n log n), and no sort that compares values can do better. Today we stop comparing. Counting sort sorts values from a small range in O(n + k) by counting them, like a teacher's tally sheet. Radix sort handles big integers by running a stable counting sort on one digit at a time, like a post office sorting letters by PIN digits. And the Dutch national flag algorithm solves the famous Sort Colors interview problem (only 0s, 1s and 2s) in one pass with O(1) extra space. Every program below was run in the SyntaxPilot compiler (8-second time limit), and the outputs shown are real.

The problem, in real life

Result day. A state board has 20 lakh students and must publish a merit list tonight, everyone sorted by marks. But every mark is a whole number from 0 to 100: twenty lakh students, only 101 possible values. That is the whole trick.

In real life As an algorithm
A teacher makes a tally sheet 0 to 100 and puts one tally per student next to the score, then reads it top to bottom Counting sort: count[x]++, then write each value count[v] times
A post office sorts lakhs of letters into 10 bins by one PIN digit, then the next digit Radix sort: a stable counting sort per digit
Sorting laundry into three piles (whites, colours, darks) in one trip through the basket Dutch national flag: low, mid, high pointers, one pass

Problem statement

  1. Sort integers from a small range. Given n integers with values in 0 .. k − 1 (or any range min .. max), sort them. Example: [4, 2, 2, 8, 3, 3, 1] → [1, 2, 2, 3, 3, 4, 8]. n can be 20 lakh.
  2. Sort records by an integer key, stably. Sort students by marks; students with equal marks keep their roll-number order.
  3. Sort Colors (LeetCode 75). An array contains only 0, 1 and 2. Sort it in place, in one pass, with O(1) extra space. Example: [2, 0, 2, 1, 1, 0] → [0, 0, 1, 1, 2, 2].

Edge cases to test: an empty array, all values equal, negative values, a single element.

Brute force: any comparison sort

The obvious approach is a sort we already know. Insertion sort (episode 16) on 3 lakh random marks:

import java.util.*;

public class Main {
    static void insertion(int[] a) {
        for (int i = 1; i < a.length; i++) {
            int key = a[i], j = i - 1;
            while (j >= 0 && a[j] > key) {
                a[j + 1] = a[j];
                j--;
            }
            a[j + 1] = key;
        }
    }
    public static void main(String[] args) {
        int n = 300000;
        int[] a = new int[n];
        Random r = new Random(1);
        for (int i = 0; i < n; i++) a[i] = r.nextInt(101);
        long t0 = System.nanoTime();
        insertion(a);
        long ms = (System.nanoTime() - t0) / 1000000;
        System.out.println(a[0] + " " + a[n - 1] + "   " + ms + " ms");
    }
}

Result: Time Limit Exceeded (it needs about 26 seconds on our machine). And the real board has 20 lakh students, not 3 lakh.

Why comparing can't beat n log n

  • n values can be arranged in n! orders, and only one of them is sorted.
  • One comparison (a < b?) is a yes/no question: at best it cuts the remaining possible orders in half, like guessing a number by asking "higher or lower?".
  • To get from n! possibilities down to 1 you need at least log₂(n!) ≈ n log₂ n questions. For n = 20 lakh that is about 4 crore comparisons.

This is the comparison-sort lower bound: merge sort and heap sort are already optimal among comparison sorts. To go faster we must stop comparing and use the fact that the values are small integers.

Counting sort: the tally sheet

Make an array count with one box per possible value. The value itself is the index.

Step What happens Example [4, 2, 2, 8, 3, 3, 1], k = 10
1. Count count[x]++ for every x count = [0, 1, 2, 2, 1, 0, 0, 0, 1, 0]
2. Write out for v = 0 .. k − 1, write v exactly count[v] times [1, 2, 2, 3, 3, 4, 8]

No two values are ever compared. One pass over the array (n) plus one pass over the boxes (k): O(n + k).

import java.util.*;

public class Main {
    static void countSort(int[] a, int k) {
        int[] count = new int[k];
        for (int x : a) count[x]++;
        int i = 0;
        for (int v = 0; v < k; v++)
            for (int c = 0; c < count[v]; c++)
                a[i++] = v;
    }
    public static void main(String[] args) {
        int[] a = {4, 2, 2, 8, 3, 3, 1};
        countSort(a, 10);
        System.out.println(Arrays.toString(a));
        int[] e = {};
        countSort(e, 10);
        System.out.println(Arrays.toString(e));
        int[] s = {7, 7, 7};
        countSort(s, 10);
        System.out.println(Arrays.toString(s));
    }
}

Output:

[1, 2, 2, 3, 3, 4, 8]
[]
[7, 7, 7]

Bug 1: a negative value

With negative marking a student can score −3. The same countSort on {4, -3, 2}:

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index -3 out of bounds for length 10
    at Main.countSort(Main.java:6)
    at Main.main(Main.java:14)

The value is the index, and there is no box number −3. Fix: find min and max, make max − min + 1 boxes, put x in box x − min, and add min back when writing out.

import java.util.*;

public class Main {
    static void countSort(int[] a) {
        if (a.length == 0) return;
        int min = a[0], max = a[0];
        for (int x : a) {
            min = Math.min(min, x);
            max = Math.max(max, x);
        }
        int[] count = new int[max - min + 1];
        for (int x : a) count[x - min]++;
        int i = 0;
        for (int v = 0; v < count.length; v++)
            for (int c = 0; c < count[v]; c++)
                a[i++] = v + min;
    }
    public static void main(String[] args) {
        int[] a = {4, -3, 2, -3, 0};
        countSort(a);
        System.out.println(Arrays.toString(a));
        int[] e = {};
        countSort(e);
        System.out.println(Arrays.toString(e));
    }
}

Output:

[-3, -3, 0, 2, 4]
[]

20 lakh marks in milliseconds

The same countSort(a) on 20 lakh random marks (r.nextInt(101), same timing code as the brute force):

0 100   32 ms

Milliseconds (the exact number changes from run to run), where insertion sort could not finish 3 lakh.

Bug 2: a huge range

Roll numbers can go up to 100 crore (10⁹). countSort on just three numbers, {170, 45, 1000000000}:

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
    at Main.countSort(Main.java:11)
    at Main.main(Main.java:20)

Line 11 is int[] count = new int[max - min + 1];: about 10⁹ boxes × 4 bytes = 4 GB. Counting sort is O(n + k) in time and memory, so when the range k is much bigger than n it is the wrong tool. That is what radix sort fixes.

Stable counting sort with prefix sums

The merit list sorts students, not bare marks: Asha 72, Ravi 45, Neha 72, Imran 90, Zoya 45 (in roll-number order). Writing bare numbers back would lose the names. We need to move whole records, and students with equal marks should keep their roll-number order: the sort must be stable.

  1. Count each mark.
  2. Prefix sums: count[v] += count[v − 1] for v = 1 .. 100. Now count[v] = number of students with marks ≤ v = one past the last seat for mark v.
  3. Place from the right: for i = n − 1 down to 0, out[--count[marks[i]]] = record i.
Walk (from the right) Mark --count[mark] Seat
Zoya 45 2 → 1 1
Imran 90 5 → 4 4
Neha 72 4 → 3 3
Ravi 45 1 → 0 0
Asha 72 3 → 2 2

The last student with a given mark gets that mark's last seat, so ties keep their input order.

import java.util.*;

public class Main {
    static String[] byMarks(String[] name, int[] marks) {
        int[] count = new int[101];
        for (int m : marks) count[m]++;
        for (int v = 1; v <= 100; v++) count[v] += count[v - 1];
        String[] out = new String[marks.length];
        for (int i = marks.length - 1; i >= 0; i--)
            out[--count[marks[i]]] = name[i] + " " + marks[i];
        return out;
    }
    public static void main(String[] args) {
        String[] name = {"Asha", "Ravi", "Neha", "Imran", "Zoya"};
        int[] marks = {72, 45, 72, 90, 45};
        System.out.println(Arrays.toString(byMarks(name, marks)));
    }
}

Output:

[Ravi 45, Zoya 45, Asha 72, Neha 72, Imran 90]

Ravi stays before Zoya and Asha before Neha: stable.

Radix sort: digit by digit

A big number is just a few digits, and each digit has only 10 values. So run a stable counting sort on one digit at a time, starting from the ones digit (LSD, least significant digit first).

Pass Key Array after the pass
start [53, 89, 20, 47, 81, 25, 9, 42]
1 ones digit [20, 81, 42, 53, 25, 47, 89, 9]
2 tens digit [9, 20, 25, 42, 47, 53, 81, 89]

In pass 2, 20 and 25 tie on the tens digit (2); pass 1 already put 20 first, and a stable pass keeps it there. That is why radix sort needs every pass to be stable.

import java.util.*;

public class Main {
    static void radix(int[] a) {
        int max = 0;
        for (int x : a) max = Math.max(max, x);
        for (int exp = 1; max / exp > 0; exp *= 10)
            byDigit(a, exp);
    }
    static void byDigit(int[] a, int exp) {
        int n = a.length;
        int[] count = new int[10], out = new int[n];
        for (int x : a) count[x / exp % 10]++;
        for (int d = 1; d < 10; d++) count[d] += count[d - 1];
        for (int i = n - 1; i >= 0; i--)
            out[--count[a[i] / exp % 10]] = a[i];
        System.arraycopy(out, 0, a, 0, n);
    }
    public static void main(String[] args) {
        int[] a = {53, 89, 20, 47, 81, 25, 9, 42};
        radix(a);
        System.out.println(Arrays.toString(a));
        int[] b = {802, 2, 170, 45};
        radix(b);
        System.out.println(Arrays.toString(b));
        int[] e = {};
        radix(e);
        System.out.println(Arrays.toString(e));
    }
}

Output:

[9, 20, 25, 42, 47, 53, 81, 89]
[2, 45, 170, 802]
[]

x / exp % 10 is the digit: exp = 1 gives the ones digit, exp = 10 the tens, and so on. This version is for non-negative values below 10⁹ (for larger values exp *= 10 would overflow an int; use long exp).

Bug 3: an unstable pass

Change the placement loop to walk forwards: for (int i = 0; i < n; i++). On {53, 89, 20, 47, 81, 25, 9, 42} it printed:

[9, 25, 20, 47, 42, 53, 89, 81]

No crash, just a wrong answer. Filling from the front with a decrementing count reverses every tie, so pass 2 scrambles the order pass 1 built.

20 lakh roll numbers

radix(a) on 20 lakh random numbers below 10⁹ (r.nextInt(1000000000)), the input range that crashed counting sort:

1065 999999944   302 ms

Nine passes over 20 lakh numbers, ten boxes each pass: a few hundred milliseconds.

Sort Colors: the Dutch national flag

Only 0, 1 and 2. A two-pass counting sort works (count, then rewrite), but the interview asks for one pass, O(1) space, swaps only. Three pointers split the array into four regions:

Region Contents
[0, low) 0s
[low, mid) 1s
[mid, high] unknown, not looked at yet
(high, n − 1] 2s

Look at a[mid]:

  • 0 → swap with a[low]; low++ and mid++ (the value that came from low is a 1, already checked).
  • 1 → mid++.
  • 2 → swap with a[high]; high-- only. mid stays: the value that came from high is unknown.

Stop when mid > high. Trace of [2, 0, 2, 1, 1, 0]:

a[mid] Action Array low, mid, high
start [2, 0, 2, 1, 1, 0] 0, 0, 5
2 swap(0, 5), high-- [0, 0, 2, 1, 1, 2] 0, 0, 4
0 swap(0, 0), low++, mid++ [0, 0, 2, 1, 1, 2] 1, 1, 4
0 swap(1, 1), low++, mid++ [0, 0, 2, 1, 1, 2] 2, 2, 4
2 swap(2, 4), high-- [0, 0, 1, 1, 2, 2] 2, 2, 3
1 mid++ 2, 3, 3
1 mid++ → mid > high, stop [0, 0, 1, 1, 2, 2] 2, 4, 3
import java.util.*;

public class Main {
    static void sortColors(int[] a) {
        int low = 0, mid = 0, high = a.length - 1;
        while (mid <= high) {
            if (a[mid] == 0) swap(a, low++, mid++);
            else if (a[mid] == 1) mid++;
            else swap(a, mid, high--);
        }
    }
    static void swap(int[] a, int i, int j) {
        int t = a[i]; a[i] = a[j]; a[j] = t;
    }
    public static void main(String[] args) {
        int[] a = {2, 0, 2, 1, 1, 0};
        sortColors(a);
        System.out.println(Arrays.toString(a));
        int[] e = {};
        sortColors(e);
        System.out.println(Arrays.toString(e));
        int[] s = {1};
        sortColors(s);
        System.out.println(Arrays.toString(s));
        int[] b = {1, 2, 0};
        sortColors(b);
        System.out.println(Arrays.toString(b));
    }
}

Output:

[0, 0, 1, 1, 2, 2]
[]
[1]
[0, 1, 2]

Bug 4: mid++ after swapping with high

Writing else swap(a, mid++, high--); (it looks symmetric with the 0 case) printed:

[0, 0, 1, 1, 2, 2]
[1, 0, 2]

The first array is still right by luck; {1, 2, 0} became [1, 0, 2]. The 2 swapped with the 0 at the end, and mid skipped past that 0 without checking it.

The same solutions in C++ and Python

C++ (counting sort for any range, radix sort, Sort Colors):

#include <bits/stdc++.h>
using namespace std;

// Counting sort for any int range: O(n + k), k = max - min + 1
void countSort(vector<int>& a) {
    if (a.empty()) return;
    int mn = *min_element(a.begin(), a.end());
    int mx = *max_element(a.begin(), a.end());
    vector<int> count(mx - mn + 1, 0);
    for (int x : a) count[x - mn]++;
    int i = 0;
    for (int v = 0; v < (int)count.size(); v++)
        for (int c = 0; c < count[v]; c++) a[i++] = v + mn;
}

// Stable LSD radix sort, base 10, non-negative ints
void byDigit(vector<int>& a, long long exp) {
    int n = a.size();
    vector<int> count(10, 0), out(n);
    for (int x : a) count[x / exp % 10]++;
    for (int d = 1; d < 10; d++) count[d] += count[d - 1];
    for (int i = n - 1; i >= 0; i--) out[--count[a[i] / exp % 10]] = a[i];
    a = out;
}
void radixSort(vector<int>& a) {
    int mx = 0;
    for (int x : a) mx = max(mx, x);
    for (long long exp = 1; mx / exp > 0; exp *= 10) byDigit(a, exp);
}

// Dutch national flag (Sort Colors): one pass, O(1) space
void sortColors(vector<int>& a) {
    int low = 0, mid = 0, high = (int)a.size() - 1;
    while (mid <= high) {
        if (a[mid] == 0) swap(a[low++], a[mid++]);
        else if (a[mid] == 1) mid++;
        else swap(a[mid], a[high--]);
    }
}

void print(const vector<int>& a) {
    cout << "[";
    for (size_t i = 0; i < a.size(); i++) cout << (i ? ", " : "") << a[i];
    cout << "]\n";
}

int main() {
    vector<int> a = {4, -3, 2, -3, 0};
    countSort(a); print(a);
    vector<int> b = {53, 89, 20, 47, 81, 25, 9, 42};
    radixSort(b); print(b);
    vector<int> c = {2, 0, 2, 1, 1, 0};
    sortColors(c); print(c);
}

Output:

[-3, -3, 0, 2, 4]
[9, 20, 25, 42, 47, 53, 81, 89]
[0, 0, 1, 1, 2, 2]

Python:

def count_sort(a):
    """Counting sort for any int range: O(n + k)."""
    if not a:
        return a
    lo, hi = min(a), max(a)
    count = [0] * (hi - lo + 1)
    for x in a:
        count[x - lo] += 1
    out = []
    for v, c in enumerate(count):
        out.extend([v + lo] * c)
    return out


def by_digit(a, exp):
    """One stable counting-sort pass on the digit (x // exp) % 10."""
    count = [0] * 10
    for x in a:
        count[x // exp % 10] += 1
    for d in range(1, 10):
        count[d] += count[d - 1]
    out = [0] * len(a)
    for x in reversed(a):          # from the right: stable
        d = x // exp % 10
        count[d] -= 1
        out[count[d]] = x
    return out


def radix_sort(a):
    """LSD radix sort, base 10, non-negative ints: O(d * (n + 10))."""
    exp, mx = 1, max(a, default=0)
    while mx // exp > 0:
        a = by_digit(a, exp)
        exp *= 10
    return a


def sort_colors(a):
    """Dutch national flag: one pass, O(1) extra space, in place."""
    low, mid, high = 0, 0, len(a) - 1
    while mid <= high:
        if a[mid] == 0:
            a[low], a[mid] = a[mid], a[low]
            low += 1
            mid += 1
        elif a[mid] == 1:
            mid += 1
        else:
            a[mid], a[high] = a[high], a[mid]
            high -= 1


print(count_sort([4, -3, 2, -3, 0]))
print(radix_sort([53, 89, 20, 47, 81, 25, 9, 42]))
c = [2, 0, 2, 1, 1, 0]
sort_colors(c)
print(c)

Output:

[-3, -3, 0, 2, 4]
[9, 20, 25, 42, 47, 53, 81, 89]
[0, 0, 1, 1, 2, 2]

Brute force vs optimal: complexity

Approach Time Extra space Stable Works on
Insertion sort (brute force) O(n²) O(1) yes anything comparable
Merge sort / Arrays.sort O(n log n) O(n) / O(log n) merge: yes anything comparable
Counting sort O(n + k) O(n + k) (O(k) for bare numbers) yes (prefix-sum version) integers in a range of size k
Radix sort (LSD, base b) O(d · (n + b)) O(n + b) yes integers / fixed-length keys with d digits
Dutch national flag O(n), one pass O(1) no exactly three key values

When to use which: counting sort when the range k is small compared with n (marks, ages, letters); radix sort for big integers with few digits (roll numbers, phone numbers, IDs); the Dutch flag for three groups in one pass (Sort Colors, partitioning around a pivot in quick sort). For general objects compared with a comparator, use an O(n log n) comparison sort.

Common mistakes

Mistake What you see Why Fix
count[x]++ with x = -3 ArrayIndexOutOfBoundsException: Index -3 out of bounds for length 10 the value is the index box x - min, size max - min + 1
Counting sort on values up to 10⁹ java.lang.OutOfMemoryError: Java heap space O(n + k) memory with a huge k radix sort, or Arrays.sort
Radix pass filling from i = 0 [9, 25, 20, 47, 42, 53, 89, 81] the pass is not stable for (int i = n - 1; i >= 0; i--)
swap(a, mid++, high--) in Sort Colors [1, 2, 0] → [1, 0, 2] the value swapped in from high is unchecked swap(a, mid, high--)
Writing bare numbers back when sorting records names lost or mismatched the write-out loop knows only values prefix sums + an out array of records
Using count[v] before the prefix-sum loop as a seat wrong positions count[v] is a frequency, not a position add count[v] += count[v - 1] first
int exp with values ≥ 10⁹ the loop never ends or skips digits exp *= 10 overflows int use long exp

Mini project: the merit list with ranks

Print the merit list highest marks first, with equal ranks for equal marks (1, 2, 3, 3, 5 ...), keeping roll order for ties. Trick: a stable counting sort on the key 100 − marks sorts by marks descending.

import java.util.*;

public class Main {
    public static void main(String[] args) {
        String[] name = {"Asha", "Ravi", "Neha", "Imran", "Zoya", "Kabir"};
        int[] marks = {72, 45, 72, 90, 45, 88};
        int n = marks.length;
        int[] count = new int[101];
        for (int m : marks) count[100 - m]++;              // key 100 - m: highest first
        for (int v = 1; v <= 100; v++) count[v] += count[v - 1];
        int[] order = new int[n];
        for (int i = n - 1; i >= 0; i--) order[--count[100 - marks[i]]] = i;
        int rank = 0;
        for (int p = 0; p < n; p++) {
            int i = order[p];
            if (p == 0 || marks[i] != marks[order[p - 1]]) rank = p + 1;
            System.out.println(rank + ". " + name[i] + " " + marks[i]);
        }
    }
}

Output:

1. Imran 90
2. Kabir 88
3. Asha 72
3. Neha 72
5. Ravi 45
5. Zoya 45

Extend it: read name marks lines from input, and print how many students got each mark (the count array before the prefix sums is exactly that histogram).

Practice

  1. Sort the letters of a lowercase string with counting sort (k = 26).
Solution
    static String sortLetters(String s) {
        int[] count = new int[26];
        for (char ch : s.toCharArray()) count[ch - 'a']++;
        StringBuilder sb = new StringBuilder();
        for (int c = 0; c < 26; c++)
            for (int k = 0; k < count[c]; k++) sb.append((char) ('a' + c));
        return sb.toString();
    }

sortLetters("syntaxpilot") printed ailnopsttxy. O(n + 26).

  1. Sort an array of only 0s and 1s in one pass with two pointers.
Solution
    static void zeroOne(int[] a) {
        int i = 0, j = a.length - 1;
        while (i < j) {
            if (a[i] == 0) i++;
            else if (a[j] == 1) j--;
            else { a[i] = 0; a[j] = 1; i++; j--; }
        }
    }

{1, 0, 1, 1, 0, 0, 1} became [0, 0, 0, 1, 1, 1, 1].

  1. Solve Sort Colors with the two-pass counting idea.
Solution
    static void colorsTwoPass(int[] a) {
        int[] c = new int[3];
        for (int x : a) c[x]++;
        int i = 0;
        for (int v = 0; v < 3; v++)
            while (c[v]-- > 0) a[i++] = v;
    }

{2, 0, 2, 1, 1, 0} became [0, 0, 1, 1, 2, 2]. Also O(n) and O(1) space, but two passes.

  1. Radix sort with base 256 (one byte per pass) for any non-negative int.
Solution
    static void radix256(int[] a) {
        int[] out = new int[a.length];
        for (int shift = 0; shift < 32; shift += 8) {
            int[] count = new int[256];
            for (int x : a) count[(x >>> shift) & 255]++;
            for (int d = 1; d < 256; d++) count[d] += count[d - 1];
            for (int i = a.length - 1; i >= 0; i--)
                out[--count[(a[i] >>> shift) & 255]] = a[i];
            System.arraycopy(out, 0, a, 0, a.length);
        }
    }

{170, 45, 1000000000, 802, 2, 66} became [2, 45, 66, 170, 802, 1000000000]. Always exactly 4 passes of O(n + 256), instead of up to 10 passes in base 10.

Quick quiz

Counting sort on {3, 0, 3, 1} with k = 4. What does count hold after the counting loop?

  • [1, 1, 0, 2]
  • [3, 0, 3, 1]
  • [0, 1, 3, 3]
  • [1, 1, 2, 0]
Answer

[1, 1, 0, 2]: one 0, one 1, no 2, two 3s. The array then becomes [0, 1, 3, 3] (the program printed exactly that).

Interview questions

  1. Can any sort beat O(n log n)? No comparison sort can (log₂ n! ≈ n log n comparisons). Counting and radix sort can, because they don't compare: they use the values as indexes.
  2. When is counting sort a bad idea? When the range k is much larger than n: O(n + k) time and memory (values up to 10⁹ → a 4 GB array).
  3. Why must each radix-sort pass be stable? Later passes break ties on a digit; stability keeps the order the earlier (less significant) digits built.
  4. LSD vs MSD radix sort? LSD starts at the least significant digit and needs stable passes over the whole array; MSD starts at the most significant digit and recursively sorts each bucket (good for strings, can stop early).
  5. In Sort Colors, why doesn't mid move after swapping with high? The value that came from high has not been examined yet.
  6. Is the Dutch national flag algorithm stable? No; long-distance swaps reorder equal keys. For bare 0/1/2 values that doesn't matter.
  7. How does this connect to quick sort? Three-way partitioning (less / equal / greater than the pivot) is the Dutch flag, and it makes quick sort fast on arrays with many duplicates.

Glossary

Term Meaning
Comparison sort A sort that only learns about the data by comparing two elements (merge, quick, insertion sort)
Lower bound The least work any algorithm of a kind must do; n log n comparisons for comparison sorts
n! (n factorial) 1 × 2 × ... × n, the number of possible orders of n distinct values
Counting sort Sorts integers by counting how many times each value occurs, then writing them out in order
Range, k The number of possible values (max − min + 1)
Frequency How many times a value appears
Prefix sum Running total: count[v] += count[v − 1], here the number of keys ≤ v
Stable Equal keys keep their original relative order
Key The part of a record we sort by (marks, a digit)
Radix The base of the number system (10 for decimal digits, 256 for bytes)
Radix sort (LSD) Sorting by each digit from least to most significant with a stable sort
exp 1, 10, 100, ...; x / exp % 10 extracts one decimal digit
Dutch national flag Partitioning into three groups (0s, 1s, 2s) in one pass; named after the flag's three stripes
low, mid, high The three pointers marking the 0s, the 1s and the unknown region, and the 2s
In-place Uses O(1) extra memory
ArrayIndexOutOfBoundsException Java's runtime error for an index outside 0 .. length − 1
OutOfMemoryError: Java heap space Java could not allocate an object because the heap (the program's memory) is full
Time Limit Exceeded (TLE) Too slow for the judge's limit (8 s in the SyntaxPilot compiler)

Summary

  • Every comparison sort needs about n log n comparisons; to go faster, stop comparing.
  • Counting sort: count[x]++, then write each value count[v] times. O(n + k). Shift by min for negative values.
  • Prefix sums plus filling from the right give a stable counting sort that moves whole records.
  • A huge range breaks counting sort (OutOfMemoryError); radix sort runs one stable counting pass per digit, O(d · (n + b)).
  • Every radix pass must be stable, or the result is wrong.
  • Sort Colors / Dutch national flag: low, mid, high, one pass, O(1) space; after swapping with high, mid stays.

Next episode: Merge intervals.