Counting sort and radix sort in Java

Problem

A million orders, a hundred zones

The courier company gets one million orders for the day. Each one has a delivery zone: a number from 0 to 99. Before the vans leave, the orders are sorted by zone, so that every van can take its own pile.

Merge sort makes about 18.7 million comparisons for a million orders, and heap sort is no better (see heap sort). They compare order with order, because they know nothing about the key.

But here you know a lot: there are only a hundred different zones. It is the same with the ratings of a product: from 1 to 5. Comparing a million orders to find out that 37 comes before 38 is work that does not have to be done at all.

The idea

Count instead of comparing

The key is a small whole number. So it can be an index into an array. The sorting becomes three passes:

Counting. One counter for each zone. Every order adds one to the counter of its zone.
Where each zone starts. Zone 0 starts at place 0. Zone 1 starts after all the orders of zone 0. Each start is the previous one plus the count of the previous zone. This is called a prefix sum.
Placing. You go over the orders left to right. Each one goes to the start of its zone, and the start moves on by one.

This is counting sort. Not a single order is compared with another one.

Going left to right has an important consequence: the orders of one zone stay in the order they came in. If they were sorted by time, inside their zone they are still by time. Such a sort is called stable. In the lesson on stability you will see why that matters so much.

See it

Eight orders, four zones

The number of zones is a parameter. For the million orders it is 100, here it is 4, so that everything is visible:

record Order(int id, int zone) {}

static Order[] byZone(Order[] orders, int zones) {
    int[] count = new int[zones];
    for (Order o : orders) {
        count[o.zone()]++;
    }
    int[] start = new int[zones];
    for (int z = 1; z < zones; z++) {
        start[z] = start[z - 1] + count[z - 1];
    }
    Order[] out = new Order[orders.length];
    for (Order o : orders) {
        out[start[o.zone()]++] = o;
    }
    return out;
}

Order[] orders = {
    new Order(101, 2),
    new Order(102, 0),
    new Order(103, 3),
    new Order(104, 2),
    new Order(105, 1),
    new Order(106, 0),
    new Order(107, 2),
    new Order(108, 3)
};
for (Order o : byZone(orders, 4)) {
    System.out.println("zone " + o.zone() + ", order " + o.id());
}

zone 0, order 102
zone 0, order 106
zone 1, order 105
zone 2, order 101
zone 2, order 104
zone 2, order 107
zone 3, order 103
zone 3, order 108

static Order[] byZone(Order[] orders, int zones) {
    int[] count = new int[zones];
    for (Order o : orders) {
        count[o.zone()]++;
    }
    int[] start = new int[zones];
    for (int z = 1; z < zones; z++) {
        start[z] = start[z - 1] + count[z - 1];
    }
    Order[] out = new Order[orders.length];
    for (Order o : orders) {
        out[start[o.zone()]++] = o;
    }
    return out;
}

Step by step, in words

Eight orders, each with a delivery zone from 0 to 3. One counter per zone, all at 0.
Counting: every order adds one to the counter of its zone. No order is compared with another one.
Where each zone starts: zone 0 at place 0, zone 1 after the two orders of zone 0, at place 2; zone 2 at 3, zone 3 at 6. Each start is the previous start plus the count of the previous zone.
Placing, left to right: 101 goes to the start of zone 2, place 3, and the start of zone 2 moves on by one.
Sorted by zone in 2n + k steps. Inside zone 2 the orders are 101, 104, 107: the order they came in. That is a stable sort.

Orders 101, 104 and 107 are in zone 2. They came in this order and went out in this order.

start[...]++ places at the current start and then moves it on by one: ++ after the expression returns the old value.

Try it

Fill in

The start of zone z is the start of the previous zone plus:

start[z] = start[z - 1] + ;

The idea

What it costs: O(n + k)

Every order is counted once and placed once: 2n steps. The starts are one per zone: k steps. In total O(n + k), where k is the number of possible keys. Memory: the array of counters (k) and the array with the result (n).

There are no comparisons here, so Bench counts every step of counting sort: every counting, every counter and every placing. Merge sort counts its comparisons:

Counting sort (zones 0–99) O(n)
Sorting (merge sort) O(n log n)

Algorithm	n = 10	n = 1,000	n = 100,000	n = 1,000,000
Counting sort (zones 0–99)	120	2,100	200,100	2,000,100
Sorting (merge sort)	21	8,709	1,536,371	18,674,993

The code runs in your browser, in JavaScript. The number of operations is the same in every language, because the algorithm is the same. The time depends on the machine, so it is only for comparison. “≈” is an estimate from the curve: we do not run an n that big, so the page does not freeze.

For a million orders counting sort makes 2,000,100 steps, and merge sort 18,674,993 comparisons. The straight line of counting sort is O(n): twice as many orders, twice the work.

More precisely, if you are curious

Can a sort by comparisons be faster than n log n? No. With n elements there are n! possible orders, and every comparison has two answers. To tell n! cases apart you need at least log₂(n!) comparisons, and that is about n log₂ n. Counting sort gets around this limit because it does not compare: it uses the key as an address.

See it

Radix sort: digit by digit

What if the key is bigger? Bulgarian postal codes have four digits, from 1000 to 9999: 9000 counters every day. Order numbers have six digits: 900,000 counters.

Radix sort sorts digit by digit with the same counting, but with only 10 counters. First by the last digit, then by the one before it, and so on to the first (LSD, from the least significant digit). Every pass is a counting sort by one digit:

static int[] byDigit(int[] codes, int exp) {
    int[] count = new int[10];
    for (int c : codes) {
        count[c / exp % 10]++;
    }
    int[] start = new int[10];
    for (int d = 1; d < 10; d++) {
        start[d] = start[d - 1] + count[d - 1];
    }
    int[] out = new int[codes.length];
    for (int c : codes) {
        out[start[c / exp % 10]++] = c;
    }
    return out;
}

int[] codes = {4003, 1504, 9000, 1000, 8001, 4000, 1404};
for (int exp = 1; exp <= 1000; exp *= 10) {
    codes = byDigit(codes, exp);
    System.out.println(Arrays.toString(codes));
}

[9000, 1000, 4000, 8001, 4003, 1504, 1404]
[9000, 1000, 4000, 8001, 4003, 1504, 1404]
[9000, 1000, 4000, 8001, 4003, 1404, 1504]
[1000, 1404, 1504, 4000, 4003, 8001, 9000]

After the first pass the codes are sorted by the last digit. After the second by the last two. After the fourth by all four.

This works only because every pass is stable. The pass by hundreds does not scramble the codes with equal hundreds, and they are already sorted by the last two digits. 1000 and 1404 and 1504 have the same first digit: the last pass leaves them in the order they got from the earlier ones.

c / exp % 10 is the digit: 4003 / 1000 is 4 with division of whole numbers, and % 10 takes the last digit.

Cost: d passes of n + 10 steps, where d is the number of digits. For six-digit numbers that is 6 · (2n + 10):

Radix sort (6 digits) O(n)
Counting sort (zones 0–99) O(n)
Sorting (merge sort) O(n log n)

Algorithm	n = 10	n = 1,000	n = 100,000	n = 1,000,000
Radix sort (6 digits)	180	12,060	1,200,060	12,000,060
Counting sort (zones 0–99)	120	2,100	200,100	2,000,100
Sorting (merge sort)	21	8,709	1,536,371	18,674,993

The code runs in your browser, in JavaScript. The number of operations is the same in every language, because the algorithm is the same. The time depends on the machine, so it is only for comparison. “≈” is an estimate from the curve: we do not run an n that big, so the page does not freeze.

Try it

Predict the output

One pass by the last digit (exp is 1). What does the program print?

int[] codes = {31, 12, 22, 11};
System.out.println(Arrays.toString(byDigit(codes, 1)));

Answer

[11, 12, 22, 31]

[11, 31, 12, 22]

[31, 11, 12, 22]

Try it

Find the bug

Someone places the orders from the back to the front. The zones come out sorted, but inside zone 2 something is not right:

static Order[] byZone(Order[] orders, int zones) {
    int[] count = new int[zones];
    for (Order o : orders) {
        count[o.zone()]++;
    }
    int[] start = new int[zones];
    for (int z = 1; z < zones; z++) {
        start[z] = start[z - 1] + count[z - 1];
    }
    Order[] out = new Order[orders.length];
    for (int i = orders.length - 1; i >= 0; i--) {
        out[start[orders[i].zone()]++] = orders[i];
    }
    return out;
}

Order[] orders = {
    new Order(101, 2),
    new Order(102, 0),
    new Order(103, 3),
    new Order(104, 2),
    new Order(105, 1),
    new Order(106, 0),
    new Order(107, 2),
    new Order(108, 3)
};
for (Order o : byZone(orders, 4)) {
    System.out.println("zone " + o.zone() + ", order " + o.id());
}

zone 0, order 106
zone 0, order 102
zone 1, order 105
zone 2, order 107
zone 2, order 104
zone 2, order 101
zone 3, order 108
zone 3, order 103

Which line is the bug on?

Pick the line with the bug.

The idea

When it does not work

k is huge. A price in euro cents up to €100,000: 10 million counters to sort a thousand orders. Merge sort will be done in about 10,000 comparisons. Counting sort pays off when k is about n or smaller.
The key is not a whole number. Names, addresses, fractional prices: they are not indexes into an array. Radix sort can sort strings character by character, but only if they all have the same length or are padded.
Negative keys. They work if you subtract the smallest one: key − min is from 0 up.

That is why the built-in sort of none of the four languages is counting sort. It has to sort anything, and the only thing it knows about the elements is how to compare them.

More precisely, if you are curious

How it is in the other languages: in Java Arrays.sort for an array of int is dual-pivot quick sort, in C# Array.Sort is introsort, in Python sort and in JavaScript sort are variants of merge sort (TimSort). They all compare. Counting sort and radix sort are written by hand when you know the key is small: zones, ratings, years, codes. How the built-in ones sort is in the lesson on stability.

Exercise

Reviews by rating

Solve the task in your editor.

Ratings from 1 to 5. Twelve reviews of a product have the ratings 5, 3, 4, 5, 1, 2, 5, 4, 4, 3, 5, 2. Count how many there are of each rating with an array of counters, print the counts, and then the ratings sorted, without a single comparison between two ratings.

1: 1
2: 2
3: 2
4: 3
5: 4
Sorted: [1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 5]

More tasks

The reviews, not just the ratings. Each review has an author and a rating. Sort the reviews by rating with byZone and check that the reviews with the same rating stay in the order they were written.
Six-digit numbers. Sort the order numbers 482113, 105990, 482100, 300001, 105911 with radix sort. How many passes do you need?
Negative temperatures. Sort the temperatures -3, 5, 0, -8, 12, 5 with counting sort. What do you subtract from every key?

Test

Check yourself

1. How many steps does counting sort make for n orders with zones from 0 to k - 1?About n · kAbout n log nAbout 2n + k: counting, the starts of the zones, placing

2. When is counting sort a bad choice?The key is a zone from 0 to 99The key is a price in euro cents up to 10,000,000, and there are 1000 ordersThe key is a rating from 1 to 5

3. Radix sort sorts the postal codes first by the last digit, then by the one before it… What must every pass keep?Nothing, every pass starts overThe order of the codes with the same digit: that way what the earlier passes sorted is not lostOnly the first digit

4. Why is counting sort not the built-in sort of the languages?Because it is not stableBecause it only works with small whole-number keys, while the built-in sort sorts anything by comparingBecause it is slow

Counting sort and radix sort

Cookies