How is counting sort a stable sort?

Question

Suppose my input is (a,b and c to distinguish between equal keys)

1 6a 8 3 6b 0 6c 4

My counting sort will save as (discarding the a,b and c info!!)

0(1) 1(1) 3(1) 4(1) 6(3) 8(1)

which will give me the result

0 1 3 4 6 6 6 8

So, how is this stable sort? I am not sure how it is "maintaining the relative order of records with equal keys."

Please explain.

Answer 1

Simple, really: instead of a simple counter for each 'bucket', it's a linked list.

That is, instead of

0(1) 1(1) 3(1) 4(1) 6(3) 8(1)

You get

0(.) 1(.) 3(.) 4(.) 6(a,b,c) 8(.)

(here I use . to denote some item in the bucket).

Then just dump them back into one sorted list:

0 1 3 4 6a 6b 6c 8

That is, when you find an item with key x, knowing that it may have other information that distinguishes it from other items with the same key, you don't just increment a counter for bucket x (which would discard all those extra information).

Instead, you have a linked list (or similarly ordered data structure with constant time amortized append) for each bucket, and you append that item to the end of the list for bucket x as you scan the input left to right.

So instead of using O(k) space for k counters, you have O(k) initially empty lists whose sum of lengths will be n at the end of the "counting" portion of the algorithm. This variant of counting sort will still be O(n + k) as before.

Answer 2

If your three "6" values are distinguishable, then your counting sort is wrong (it discards information about the values, which a true sort doesn't do, because a true sort only re-orders the values).

If your three "6" values are not distinguishable, then the sort is stable, because you have three indistinguishable "6"s in the input, and three in the output. It's meaningless to talk about whether they have or have not been "re-ordered": they're identical.

The concept of non-stability only applies when the values have some associated information which does not participate in the order. For instance if you were sorting pointers to those integers, then you could "tell the difference" between the three 6s by looking at their different addresses. Then it would be meaningful to ask whether any particular sort was stable. A counting sort based on the integer values then would not be sorting the pointers. A counting sort based on the pointer values would not order them by integer value, rather by address.