A nightly ingest sorts last night’s HTTP access rows by status code before a dashboard groups them. Status is an int from 100 to 599. The job calls Arrays.sort with Comparator.comparingInt(Access::status) on every flush. Fifty thousand staging lines finish in a blink. Eight million production lines still compare keys whose universe is five hundred values.

Nobody wrote a bad comparator. They ranked a small key universe with a comparison sort.

Counting sort ranks by frequency: histogram the keys, take a prefix of the counts, then place each item into its rank. Legal when k is small — a byte, a status enum, scores 0–100. Not a comparison sort. The Algorithms Roadmap owns families and the glossary. Here we only care about a small universe, the histogram, and the ranks that fall out of a prefix of counts.

The comparison sort on a 500-value key

Arrays.sort on objects is a comparison procedure (Timsort). Primitive int[] is too (quicksort). Both ask, repeatedly, “is this key less than that key?” That question is the right primitive when keys are arbitrary Comparables. It is the wrong bill when every key is an integer from a known, tiny range.

HTTP status, a five-value payment enum, a quiz score 0–100, a byte: you can count how many items hold each value. Once you know the frequencies, you know the ranks. You never compare two keys.

Note: k is the size of the key universe after you map it onto 0 .. k-1, not “the largest int Java can store.” Status 100–599 is k = 500 with offset 100. Scores 0–100 are k = 101. All 32-bit ints are k ≈ 2³² — that is not this algorithm.

Histogram, prefix, place

Three passes. That is the whole procedure.

  1. Histogram. count[key]++ for every item. count[v] is how many items have key v.
  2. Prefix. Running sum: count[i] becomes the number of items with key ≤ i. That number is the exclusive end of v’s slot in the output.
  3. Place. Walk the input from the right. For each item, decrement count[key] and write the item into out at that index.

After the prefix, keys 0 .. v-1 occupy out[0 .. count[v-1]), and key v occupies out[count[v-1] .. count[v]). Placing from the right fills each slot from its end backward, so equal keys keep the order they had in the input. That is the contract radix sort needs from a digit pass.

Keys that are not already 0 .. k-1 take an offset: key = status - 100. Negative keys are legal if you shift the floor to zero first. Sparse keys that still sit in a small min–max range are the same offset. Sparse keys whose min–max is “all ints” are a different job.

A walk: scores 0–4

Seven submissions. Key universe 0 .. 4, so k = 5. Place from the right.

a (score as filed):
  [3, 1, 3, 0, 1, 3, 2]
   0  1  2  3  4  5  6

histogram count[v] = how many scores equal v:
  v:      0  1  2  3  4
  count:  1  2  1  3  0

prefix count[i] = how many scores are <= i
  (exclusive end of key i's output slot):
  v:      0  1  2  3  4
  count:  1  3  4  7  7

place from the right (i = 6 .. 0):
  i=6 x=2  count[2]=4 → 3   out[3]=2
  i=5 x=3  count[3]=7 → 6   out[6]=3
  i=4 x=1  count[1]=3 → 2   out[2]=1
  i=3 x=0  count[0]=1 → 0   out[0]=0
  i=2 x=3  count[3]=6 → 5   out[5]=3
  i=1 x=1  count[1]=2 → 1   out[1]=1
  i=0 x=3  count[3]=5 → 4   out[4]=3

out:
  [0, 1, 1, 2, 3, 3, 3]

slots from the prefix (exclusive ends 1, 3, 4, 7, 7):
  key 0: [0]
  key 1: [1, 1]
  key 2: [2]
  key 3: [3, 3, 3]
  key 4: (empty)

The two 1s keep filing order: the 1 from index 1 sits left of the 1 from index 4. The three 3s keep filing order too: index 0, then 2, then 5 land in out[4], out[5], out[6].

Same prefix, place from the left, and the equals reverse. The histogram does not change; the place direction is the algorithm.

place from the left (i = 0 .. 6), decrement the same prefix:
  i=0 x=3  count[3]=7 → 6   out[6]=3   first 3 lands last in its slot
  …
  the three 3s finish as i=5, i=2, i=0 in out[4..6] — reversed

If the items were records (score, studentId), the output must be sorted by score and, among a tied score, still in arrival order. Status 200 rows in the access log stay in the order they were written. Start i at n - 1.

Java sketch

A row is a status and a path. The universe is 100–599. Offset 100, k = 500.

record Access(int status, String path) {}

static Access[] countingSort(Access[] a, int minKey, int k) {
    int[] count = new int[k];
    for (Access row : a) {
        count[row.status() - minKey]++;
    }
    for (int v = 1; v < k; v++) {
        count[v] += count[v - 1];
    }
    Access[] out = new Access[a.length];
    for (int i = a.length - 1; i >= 0; i--) {
        int key = a[i].status() - minKey;
        count[key]--;
        out[count[key]] = a[i];
    }
    return out;
}

Access[] ranked = countingSort(rows, 100, 500);

Primitive scores 0 .. 100 are the same loop with no offset and k = 101:

static int[] countingSort(int[] a, int k) {
    int[] count = new int[k];
    for (int x : a) {
        count[x]++;
    }
    for (int v = 1; v < k; v++) {
        count[v] += count[v - 1];
    }
    int[] out = new int[a.length];
    for (int i = a.length - 1; i >= 0; i--) {
        int x = a[i];
        count[x]--;
        out[count[x]] = x;
    }
    return out;
}

The output array is required in this formulation: the place pass reads a[i] while it writes out. Do not overwrite a in the same pass unless you have proven the slots cannot clobber unread keys — that is a different sketch, and it is usually not worth the cleverness on the ingest path.

A payment enum is the same offset with k = values().length and key = status.ordinal(). A byte (or byte payload you promote to 0 .. 255) is k = 256 and no offset. Do not box the byte[] into Byte[] so a comparison sort can run.

Note: A key outside minKey .. minKey + k - 1 is an ArrayIndexOutOfBoundsException, not a sort of the rest. Validate or clamp at the boundary. An empty input returns an empty out. All keys equal: the prefix is n in one bucket, and the place pass copies a into out in original order. Scan once for min / max if the range is small but unknown; if that scan says max - min is huge, stop — you do not have a counting-sort universe.

Complexity

No key is compared to another key. Time is linear in the items plus linear in the universe.

TimeO(n + k)
Extra spaceO(n + k) — output plus histogram
StableYes, when you place from the right
In-placeNot in this formulation
Key comparisonsNone

When k is 500 and n is eight million, n + k is the ingest you wanted. When k is 2³¹ and n is a thousand, the histogram is the bill. Comparison sort’s O(n log n) wins that fight without allocating a two-billion-slot array. Three linear passes over n, plus one linear pass over k for the prefix: there is no log n because you never split a comparison tree.

O(n + k) is the selling point only while k is small next to the comparison-sort bill.

The extra array is the usual cost of a stable place. You can overwrite count during the place pass; you cannot overwrite a without a different invariant. On the ingest path, allocate out and return it.

When not to use counting sort

Skip the histogram when the universe is not small, or the keys are not integers you can bucket:

  • All ints as the universe. k is huge. You cannot afford count[]. Call Arrays.sort.
  • Tiny n. A dozen rows. The JDK comparison sort is the clearer line, and the constant factors do not matter.
  • No integer key. A Comparator over two fields, a locale-sensitive String, a LocalDateTime with no compact encoding. There is nothing to histogram.
  • You only needed a histogram. The dashboard that groups by status already has count[] after pass one. Sorting the rows is a different job. If the product is “how many 404s,” stop after the tally.
  • The key changes after you ranked. Counting sort is an offline rank of a snapshot. A live stream of status updates needs a structure that inserts; re-running the three passes on every event is correct at hundreds of rows and the wrong default at eight million.

Counting sort is for “rank these items by a small integer key.” It is not a faster Arrays.sort you sprinkle on every list.

JDK: there is no CountingSort class

The library you already have is comparison sort:

  • Object arrays and lists: Arrays.sort / List.sort — Timsort
  • Primitive arrays: Arrays.sort — Dual-Pivot Quicksort

There is no java.util.CountingSort. When the universe is small, you write the three passes. When it is not, you call Arrays.sort and do not apologize.

int[] of scores 0–100 is a legitimate hand-roll. Access[] ordered by status is too. List<Invoice> ordered by BigDecimal amount is not — that stays the JDK comparison sort. A byte[] is a 256-bucket universe; counting sort is the natural rank. Do not wrap that byte[] in Byte objects so Timsort can compare them.

Collections.sort / List.sort are the same Timsort story on a List. There is still no counting-sort overload. IntStream and sorted() are comparison. If the ingest already has an int[] of codes, rank that array; do not copy into a List<Integer> first.

Write a histogram when k is small and known. Call Arrays.sort when it is not.

Cheat sheet

Job:        rank items whose keys sit in 0 .. k-1 (or min .. min+k-1)
Pass 1:     count[key]++
Pass 2:     prefix — count[i] = how many keys are <= i
Pass 3:     place from the right into out[count[key]-1]
Time:       O(n + k)     extra space: O(n + k)
Stable:     yes, if you place from the right (radix depends on this)
Not this:   comparison sort; all-ints universe; tiny n
JDK:        no CountingSort; Arrays.sort is Timsort / Dual-Pivot Quicksort

Do:

  • Map the key onto 0 .. k-1 with an offset, then histogram.
  • Place from the right so equal keys keep input order.
  • Use this when k is a byte, an enum ordinal, a score, or HTTP status.
  • Scan min/max first only when the range is unknown and you will abort if max - min is huge.

Don’t:

  • Allocate count over all 32-bit ints and call it counting sort.
  • Place from the left and then promise radix a stable digit pass.
  • Replace Arrays.sort on arbitrary objects because this post has “sort” in the title.

Wrap-up

Counting sort is a rank, not a comparison. Histogram the small universe, prefix the counts, place each item into its slot. Place from the right and equal keys keep arrival order — that is why a digit pass can reuse this loop. The bill is O(n + k). When k is huge, the histogram is the wrong allocation and Arrays.sort is the procedure you already have.

Use it on status codes, enums, scores, bytes. Skip it when the key does not fit in a small table. The eight-million-row ingest with status 100–599 is this procedure. The same ingest with a Comparator over path plus timestamp is Timsort. The next post is the reason the place-from-the-right pass exists: several of these ranks, one per digit.

Next optional step in the series Digit passes when comparison is the wrong primitive. Radix Sort: Digit Passes