`We have seen various algorithms for sorting with time complexity O(n log n) and a lower bound showing that O(n log n) is optimal. But the lower bound only applies to comparison sorting. What if we're allowed to do other operations than comparisons?`

Let's start with a really simple example: We want to sort n integers that are all in the range 1..n, no two the same. How quickly can we determine the sorted order?

Answer: O(1), without even computing anything you know it has to be 1,2,3,...n-1,n.

Counting Sort works by counting the occurrences of each data value. It assumes that there are *n* data items in the range of 1..*k*, where *k* is an integer. The algorithm can then determine, for each input element, the amount of elements less than it.

sort(int k, X[n])

{

int i,j, Y[k+1]

`for (i = 0; i <= k; i++) Y[i] = 0;`

for (i = 0; i < n; i++) Y[X[i]]++;

for (i = 0, j = 0; i <= k; i++)

while(Y[i]-- > 0) X[j++] = i

}

All the three loops perform in O(n), but there might be a doubt for the last loop since it is nested.

One not-completely-obvious point: one of the loops is nested. Normally when we see a collection of nested loops, the time bound is the product of the number of iterations of each loop. Why is this nested loop O(n) rather than O(n^2)?

Answer: It's possible for the inner loop to execute as many as n times, but not on all n iterations of the outer loop. The easiest way to see this is to match up the times when we increment the array entries with the times when we decrement them. Since there are only n increments, there are also only n decrements.

We say that a sorting algorithm is *stable* if, when two records have the same key, they stay in their original order. So, counting sort is stable, since we add items to the lists Y[i] in order, and concatenating them preserves that order.

< Previous | Next > |
---|

To avoid waiting for your comment to be published after being reviewed, please log in as a registered user.