Can sorting be done in time complexity of O(n). The answer is Yes. But, the shortcoming is that the toll it takes on the space. As you will go through the algorithm and notice, if the input array contains numbers whose range is way more than the size of the array, the technique can be very hard on space. But anyways, here’s the algorithm if the size of the numbers and the range of the numbers isn’t very large.

**Algorithm**

1. Create an array of size max(input)+1 to account for the element 0. This array will store the **frequency** of input numbers at it’s index, e.g. if element 2 occurs 3 times in the input, then count[2] = 3

2. Iterate through the count array and create a cumulative sum that will determine the position in the input numbers in the output array

3. Now iterate through the input array, get it’s position from the count array and store the number at position-1 in the output array. Decrement the count by 1 so the next occurrence of the number is stored at the corresponding prior position

**Code**

def countSort(nums):
max_n = max(nums)
len_n = len(nums)
count = [0] * (max_n+1) # Account an extra space for element 0
output = [0] * len_n
# Set the frequency of input numbers in the count array
for n in nums:
count[n] += 1
# Create cumulative sum in the count array to get the position of the next number in the output array
for i in range(1, max_n+1):
count[i] += count[i-1]
# Iterate through input, get the pos for output and store in output; decrement the count so next number is stored at a different position
for n in nums:
pos = count[n]
output[pos-1] = n
count[n] -= 1
return output
nums = [1,2,5,2,3,1]
result = countSort(nums)
print(f'Counted Sort on {nums} is {result} | {result== [1, 1, 2, 2, 3, 5]}')
nums = [4,8,10,2,5,1,9,2,7,1]
result = countSort(nums)
print(f'Counted Sort on {nums} is {result} | {result==[1, 1, 2, 2, 4, 5, 7, 8, 9, 10]}')