Sorting of 1 million integers ranging from 1 to 9 using Java code

Question

Given a collection of 1 million integers between 1 to 9. How would you sort them in an efficient manner ?

Input: [1,2,5,4,7,8,9,6,5,4,2,3,6,5,8]  
Output: [1,2,2,3,4,4,5,5,5,6,6,7,8,8,9]

Answer 1

For big inputs, Java's Collections.sort() uses TimSort, which runs on O(n log(n)). If you want it to run faster, let's say linear time, than you should use a non-comparison based sorting algorithm.

Since your range of integers is much smaller than the number of items to sort, that's the perfect usage for Counting Sort.

Being k = 9 (range from 1-9) and N = 1 million. Your running time would be O(k + N).