Sort repeating numbers

Question

 int a[] = {0, 0, 0, 0, 0, 0, 1, 1, 2, 0, 0, 2, 1, 1, 0, 0, 0, 2, 2, 1, 1, 1, 0, 0, 0, 0, 0, 0};

What is the best approach to sort such series? Keep in mind I want the minimum complexity.

Answer 1

If the numbers have a small upper limit, you can use a counting sort: count how many times each item appears in the array, then walk through the array, and put in as many items as you counted for each of the values.

For example, in your case you would count 17 zeros, 7 ones, and 4 twos. Set the first 17 items to 0, the following 7 to 1, and the remaining 4 to 2 to get a sorted array.

This approach has linear complexity.