is O(n) worst case? if it is you might wanna try radix sort, counting sort or some other non-comparison based sorting technique.