DEV Community

Counting Linearly With Counting Sort

Vaidehi Joshi on July 17, 2017

If there’s one question that every developer finds themselves asking on a daily basis, it must be this: is it possible to make this better? In almo...

Read full post

Palle • Jul 24 '17 • Edited

There are also other Θ(n) (linear runtime in best, average and worst case) sorting algorithms. The most popular one may be radix sort.

You sort an array digit by digit by partitioning it into buckets, one bucket for each digit. This step is repeated from least significant to most significant digit, so for k-bit integers, the runtime of the algorithm is Θ(n*k)

As only the partially solved array and buckets for the next iteration need to be stored, the algorithm is more space efficient, requiring only Θ(n) additional space.

An example in base 10 would be:

Input array:
[637850, 18387, 329361, 968160, 183352, 296430, 56942, 990013, 663578, 792961]

The array is partitioned into ten buckets based on the 0th digit (from the right):
[637850, 968160, 296430],[329361, 792961],[183352, 56942],[990013],[],[],[],[18387],[663578],[]

The partitioned array is then flattened and the process is repeated with the 1st digit:
[],[990013],[],[296430],[56942],[637850, 183352],[968160, 329361, 792961],[663578],[18387],[]

2. digit:
[990013],[968160],[],[183352, 329361, 18387],[296430],[663578],[],[],[637850],[56942, 792961]

3. digit:
[990013],[],[792961],[183352, 663578],[],[],[296430, 56942],[637850],[968160, 18387],[329361]

4. digit:
[],[18387],[329361],[637850],[],[56942],[663578, 968160],[],[183352],[990013, 792961, 296430]

5. digit:
[18387, 56942],[183352],[296430],[329361],[],[],[637850, 663578],[792961],[],[968160, 990013]

The array is flattened and we're done:

[18387, 56942, 183352, 296430, 329361, 637850, 663578, 792961, 968160, 990013]

Like counting sort it is also stable, out of place and not based on comparisons. It can even be extended to sort floating point numbers and strings.

Edit:
It also sounds awesome

Vaidehi Joshi • Jul 24 '17

Hi Palle,

I actually just wrote this week's post on radix sort, funnily enough ☺️ You can read it here: medium.com/basecs/getting-to-the-r...

Vaidehi

Vandana-V • Dec 27 '17

I really love the way you break down complex concepts into simpler ones with a wild real-world mapping.

However this counting sort is kinda confusing in the sense I've read some resources that say one can apply counting sort only if 'k'(the highest no. in the array) is less than 'n'(the total no. of elements in the array). And even you have mentioned it while explaining its space complexity. However, in your example the highest is 9 and the no. of array elements is 8. Yet we proceeded with counting sort. Is it due to some other governing factor? And why do we have to shift the elements in our count array?

I would love to wrap my head around this concept. Could you please help me out with this?

Ben Halpern • Jul 24 '17

I had never heard of counting sort before.

Vaidehi Joshi • Jul 24 '17

It is, perhaps, my favorite sort. But at least 50% of my love for it comes from the cute sheep that I have now mentally associated with counting sort 😛