Sort array of duplicate integers in place Given an array of integers within [1, n] where n = size of array, some elements may appear more than once.

Could we sort it with just 1 extra space and in O(n) time?
Use Radix sort. The time complexity is O(kn) and space complexity is O(k + n) . Here n is the number of elements and k is the number of bits required to represent largest element in the array.