Counting Sort

Counting Sort is an integer sorting algorithm. It is not very famous when somebody talks about sorting algorithms but it is great when sorting integers. In fact, many a times it may even beat other Sorting Algorithms. The highlight of Counting Sort is that it creates a bucket array (to keep track of frequency of numbers) whose size is the maximum element in the provided array.

We are looking to compare most of the sorting algorithms to find out which one performs better under different circumstances. One of the ways is to compare the complexity for each algorithm. The other way is to compare how well they perform based on the input they are all provided. I will post my code on Github but will start with Counting Sort here.

Here are some pointers about Counting Sort:

How do we compare all Sorting Algorithms?

We are going to look at the following scenarios across all Sorting Algorithms:

Machine Setup

The setup of my machine is as follows:

| Hardware: x86_64 | Processor: 16 x Intel® Xeon® E5540 2.53 GHz | Compiler: gcc version 4.8.2 (GCC) | Redhat Version: Red Hat 5.3

The Source Code

I am trying to do this all together in a single place so that it is easy for anybody to pick up the code, either for their own testing or going through the Sorting Algos. All of the source code for this can be found here:


Without further ado, let’s delve into the numbers for Counting Sorts. Here’s the result from the code:

# of Items in Array Time Taken Average for 100 numbers
Random 10 0.022982 0.22982
1K 1.21822 0.121822
1M 1823.85 0.182385
Sorted 10 0.026815 0.26815
1K 1.19146 0.119146
1M 1612.58 0.161258

comments powered by Disqus