Counting Sort

How can counting tell a whole card where to go?

Counting Sort orders records by small-range integer keys. It counts each key, adds those counts into group boundaries, and uses those boundaries to place the original records. There is no comparison between one card’s key and another’s.

Our five cards are:

Input index    0    1    2    3    4
Card          3A   1B   3C   0D   1E

The number is the sorting key. The letter identifies an original card; it is not a second sort key. Sorting the keys should give 0, 1, 1, 3, 3. A stable result also keeps B before E and A before C, because that was their order in the input.

We will produce 0D, 1B, 1E, 3A, 3C, without changing the input list. This matters for real records: a key might be a priority, while the rest of the card contains a message or a person’s details.

The video is not public yet. The complete written explanation, Python example and adjustable lab are ready to use.

First count how much room each group needs

This implementation accepts keys from 0 through K - 1. With K = 4, create four counters, including one for key 2 even though it never appears.

Read the input from left to right. A’s key 3 changes the key-3 counter from 0 to 1. B increments key 1; C increments key 3 again; D increments key 0; E increments key 1 again.

After reading any number of cards, counts[k] is the number of cards with key k read so far. The letters and the input remain intact.

Five input cards need five output slots. Their frequencies reserve these widths:

Output index     0  |  1    2  |  3    4
Reserved key     0  |  1    1  |  3    3
Group width      1  |     2    |     2

Key 2 gets zero slots, not an extra empty slot. Knowing that the ones need two places is still not enough: we must include the space occupied by the zero before them.

Prefix sums turn widths into boundaries

Add frequencies from left to right:

These running totals are prefix sums. Each value now counts all cards with keys at most that key. There are three cards with key 0 or 1, so the ones finish after the first three slots.

A total of three is an exclusive end boundary, not output index 3:

Index       0    1    2  |  3    4
Key         0    1    1  |  3    3
                        ↑
                   end boundary 3

Our indexes start at zero. Boundary 3 sits after index 2, so subtracting one gives the last available place for a one. Key 2 also has end 3: its group starts and ends at the same boundary.

Decrement the end, then place the whole record

Fill each group from its right end. To preserve the order of equal cards, read the input from right to left.

Start with 1E. Its key selects counts[1] = 3. Decrement that entry to 2, then assign the entire E record to output[2]. B came earlier and still has the earlier slot available.

None means an empty output slot. Zero is a real key, so it cannot safely stand for emptiness.

During placement, each counter is the boundary after the still-free part of its key’s group. Decrementing it claims exactly one free position. Different key groups do not overlap, and their widths add up to the number of input cards. After all five writes, every slot is filled once.

The counters finish as [0, 1, 3, 3], the original group starts. They do not need to become all zeroes. A filled output establishes completion.

Why does the backward walk preserve stability?

E is the later card with key 1, so it takes the later slot for key 1 first. When B is visited, that group’s end has moved left. B takes index 1, before E at index 2. The same argument keeps A before C.

If we walked forward while still decrementing ends, B would take index 2 first and E would take index 1 afterward. The keys would be sorted, but their original equal-key order would be reversed.

Backward scanning is paired with this choice of end boundaries. Another stable implementation can scan forward, fill each group from its start, and increment the start. Do not change only the scan direction while keeping the rest of this code.

The complete Python implementation

The contract is explicit: K is a nonnegative integer, and every record has an integer key in 0 <= key < K. This small teaching function assumes that contract; validate it before calling the function with untrusted input. The lab checks it before changing the current run.

def counting_sort(items, K):
    counts = [0] * K
    for key, _ in items:
        counts[key] += 1

    for key in range(1, K):
        counts[key] += counts[key - 1]

    output = [None] * len(items)
    for item in reversed(items):
        key = item[0]
        counts[key] -= 1
        output[counts[key]] = item

    return output


cards = [(3, "A"), (1, "B"), (3, "C"), (0, "D"), (1, "E")]
print(counting_sort(cards, K=4))
# [(0, 'D'), (1, 'B'), (1, 'E'), (3, 'A'), (3, 'C')]

The underscore ignores the letter while counting. The full tuples remain in items, and placement assigns those original tuple references to output. reversed(items) walks the existing list; it does not build a second input list.

Download the Python example or inspect the tested companion at its exact revision.

An empty input returns an empty output; K = 0 is valid in that case. A single key-zero card needs K >= 1. Duplicate cards are separate original records even when all their keys match.

Count work and storage separately

Let n be the number of cards and K the number of allowed key slots.

There are a fixed number of passes over these two sizes, with constant work per visited item under the usual fixed-size key/reference model. Time is O(n + K). This is linear in n only when the key-range cost is suitably bounded, such as K = O(n).

At the same time, the algorithm keeps K counter entries and n output references. It reuses the counter list when frequencies become ends. Extra space including the returned output is O(n + K); workspace excluding that output is O(K). The existing input and the lab’s saved teaching snapshots are not part of those extra algorithm-storage counts.

A small number of keys is not always a small range

Our example has three distinct keys, five cards, and four key slots. Those are different quantities. Setting K = 8 for the same cards creates eight counters, including unused keys 4 through 7.

Five cards spread from 0 to 1,000,000 would require 1,000,001 counters in this implementation. That range can make Counting Sort a poor choice even though there are very few cards. The lab caps the displayed range at 16 counters and explains the limit instead of allocating a huge array.

An offset is an extension to the shown code. For keys from −2 to 1, use key - (-2) to address counters 0 through 3, while preserving the original key in the record. With offsets, the range width is maximum - minimum + 1. Finding those bounds adds an input pass. Large values close together can be cheap: 1,000,000 and 1,000,001 need only two counter slots after offsetting. Wide gaps cause the problem.

Try to explain the next step

• Why does key 2 still need a counter even though it gets no output slots?
• Why does boundary 3 lead to output index 2 for E?
• Before B is placed, which counter tells you its destination? What must change first?
• Why does replacing reversed(items) with items break stability here?
• In the wide-range preset, which work increases when n stays fixed and K grows?

Use the lab to test your answers. Stepping, reading and changing inputs do not mark the concept learned. The “I understand this concept” control is an explicit, reversible mark.

Continue learning and practice

Review direct addressing for why a key can select a counter directly, or prefix-sum arrays for accumulated counts. Radix Sort builds on stable passes; Merge Sort shows a comparison-based alternative without one counter per possible key.

Practice the counting idea in Relative Sort Array, LeetCode 1122. Its requested order comes from a second array, followed by remaining values in ascending order. That is a different output contract from this lesson’s ordinary ascending sort. The Counting Sort learning path connects the lesson, prerequisites and practice.

Sources and variant boundaries

This explanation and five-card trace are original and checked against the executable Python model. Wellesley’s linear-sorting notes discuss records, group allocation, stability and range-sensitive cost. Their pseudocode uses one-based positions; the zero-based implementation here decrements an exclusive end before writing. Keep the indexing convention and update order together.