Skip to main content

Counting Sort and When Integer Keys Break the Lower Bound

What This Concept Is​

Counting sort assumes integer keys in a known range of R consecutive values. Count each key, compute prefix offsets, then place complete records into an output array. Time is Theta(n+R), and a stable record implementation uses O(n+R) extra slots. The range width R is not the number of distinct observed keys.

One stable placement uses exclusive starting offsets and scans input left to right, incrementing the chosen key's offset after each placement. Another uses inclusive ending counts and scans right to left. Mixing those directions reverses ties.

Why It Matters Here​

This is a concrete example of trading a stronger input contract for a different cost. It also separates counting categories from sorting records. A histogram does not retain payloads or their arrival order, even if expanding its counts would reproduce the sorted keys.

Concrete Examples​

Input (2,A),(0,B),(2,C),(1,D) has counts [1,1,2], starting offsets [0,1,2]. Place A at 2, B at 0, C at 3, and D at 1. Output is (0,B),(1,D),(2,A),(2,C). The invariant is that each key's already placed records occupy the next prefix of its reserved segment in arrival order.

For keys from -2 through 2, index key+2 and allocate five counters. For just two observed keys, 0 and 10^12, a dense counter array still needs 10^12+1 entries. Coordinate compression first needs a way to establish key order; sorting the distinct keys must be included in the end-to-end cost.

Common Confusion / Misconceptions​

Theta(n+R) does not imply faster wall-clock execution whenever R=O(n). Constants, key extraction, initialization, and memory traffic matter. Counting sort and deterministic radix sort do not require random input. Bucket sorting with per-bucket insertion sort is a different algorithm whose expected bounds depend on a distribution; an expectation alone is not a high-probability claim.

How To Use It​

Specify allowed keys, negative-key translation, stable record behavior, and memory budget before allocating counters. If only a histogram is required, omit the output-record buffer and say that the output contract changed. Use separate key and payload fields so numeric sorting does not destroy record association.

Check Yourself​

  1. Why are n and R independent parameters?
  2. Why does a stable record sort need more than a count array?
  3. Which placement direction matches exclusive starting offsets?
  4. What preprocessing does coordinate compression hide?

Mini Drill or Application​

Implement stable counting sort for keys -3 through 3, using tagged records. Check empty input, both endpoints, and repeated keys. Derive the loop invariant for your placement direction. Then estimate counter and output-reference bytes under explicitly stated slot sizes; distinguish those from payload storage. See P4 and the optional radix extension.

Read This Only If Stuck​

Use CLRS, Skiena, or Sedgewick and Wayne for stable counting sort, prefix offsets, and key-range assumptions. These links open book indexes; find the named topic in your edition. Use the reading guide for the bounded assignment and worked examples before adding another source.