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
- Sort integers from a small range. Given
nintegers with values in0 .. k − 1(or any rangemin .. max), sort them. Example:[4, 2, 2, 8, 3, 3, 1] → [1, 2, 2, 3, 3, 4, 8].ncan be 20 lakh. - Sort records by an integer key, stably. Sort students by marks; students with equal marks keep their roll-number order.
- Sort Colors (LeetCode 75). An array contains only
0,1and2. 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
nvalues can be arranged inn!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 leastlog₂(n!) ≈ n log₂ nquestions. 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.
- Count each mark.
- Prefix sums:
count[v] += count[v − 1]forv = 1 .. 100. Nowcount[v]= number of students with marks ≤ v = one past the last seat for markv. - 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++andmid++(the value that came fromlowis a 1, already checked). - 1 →
mid++. - 2 → swap with
a[high];high--only.midstays: the value that came fromhighis 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
- 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).
- 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].
- 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.
- 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
- 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.
- 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).
- 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.
- 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).
- In Sort Colors, why doesn't
midmove after swapping withhigh? The value that came fromhighhas not been examined yet. - Is the Dutch national flag algorithm stable? No; long-distance swaps reorder equal keys. For bare 0/1/2 values that doesn't matter.
- 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 valuecount[v]times. O(n + k). Shift byminfor 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 withhigh,midstays.
Next episode: Merge intervals.