Sorting an integer array of 100 elements having only 3 elements in it

Question

Suppose I have an array of 100 numbers. The only distinct values in the array are 1, 2 and 3. The values are randomly ordered throughout the array. For instance, the array might be populated as:

int values[100];

for (int i = 0; i < 100; i++)
    values[i] = 1 + rand() % 3;

How can I efficiently sort an array like this?

Answer 1

The fastest solution is not to "sort" at all:

• Run through the array and count the number of occurrences of 1,2 and 3. These counts should hopefully fit in registers...
• Fill the array with the right number of 1s, 2s and 3s, overwriting whatever is there already.

At the end you will have a fully sorted array.

In general, this can be a useful O(n) sorting algorithm when you have a very small range of possible values compared to the size of the array.