This page assumes nothing. Before you touch the parent note, every letter, box and arrow it uses is built here from the ground up. Read top to bottom — each idea is the soil the next one grows in.
Two things an array lets you do, and we will lean on both:
Read/write by address in one step. "Put 9 in box 3" is instant — you don't walk the row looking for box 3, you jump there. This is called random access and costs O(1) (we define O(⋅) below).
Use a value as an address. If a value happens to be a small whole number like 3, we are allowed to say "go to box 3." This tiny trick is the entire secret of counting sort — a value becomes an address.
Picture it as the length of the input row. Every "scan the input once" in the parent costs about n steps — one visit per box. We need a name for that count so we can talk about speed.
Why does the topic need a separate letter from n? Because n (how many items) and k (how spread out their values are) are independent. You can have n=3 items whose values are 0 and 1000000 — tiny n, huge k. The whole "when is counting sort a good idea?" question is really "is k small compared to n?"
Picture a luggage tag: the number on the tag is the key, the suitcase is the element. Counting sort only ever reads the tag number to decide where the suitcase goes. This is why the parent can sort records, not just bare numbers.
Why the topic needs it: to place a value you must first know how many copies of it (and everything below it) exist. Step 1 gathers that raw information.
This is the cleverest borrowed tool, so we build it slowly.
count[v]←∑i=0vcount[i]
Why this tool and not another? We need, for every value, the number of smaller-or-equal elements. A prefix sum is the one O(k) pass that computes all those running totals at once — no repeated re-adding.
Picture two suitcases both tagged 0: one labelled b, one labelled d, with b originally in front. A stable sort guarantees b still sits before d afterwards. This is why the parent scans the input right-to-left when placing — so the last equal element grabs the last slot and order is preserved. Stability is what lets counting sort be reused digit-by-digit inside Radix Sort.
Why the topic needs it: we want to say counting sort is fast without pinning it to one computer's clock. O(n+k) captures the shape: cheap when k is small, ruinous when k explodes.
