COMP1927 - Key Index Sort / Count Sort

Key Index Sorts are non-comparative. This means that instead of comparing elements to each other, elements are sorted using the 'key' as an index.'

For instance in a list of numbers where we know the range the numbers can be tallied using an array. Every time a number is encountered array[number] is incremented.

Type

Non-Adaptive
Stability isn't an issue; ordering is ignored in a tally
In-Place

Complexity

The lower bound of complexity is O(n) depending on what the key is.

Example

921.11.counting-sort.GIF

Code

void countSort (int array[], int length, int smallest, int biggest) {
 
   int tally = calloc(biggest-smallest, sizeof(int));
 
   int i;
   for (i = 0; i < length; i++) {
      tally[array[i]]++;
   }
 
   int numSorted;
   int j;
   for (i = smallest; i < biggest; i++) {
      for (j = 0; j < tally[i]; j++) {
         array[numSorted] = i;
         numSorted++;
      }
   }
 
}