No, you can not sort in O(n) time. Sorting requires comparison and reinsertion of items, so it is almost impossible to do it in O(n) time unless you are starting off with empty or already sorted array.