def counting_sort(arr):
m = min(arr)<EOL>different = <NUM_LIT:0><EOL>if m < <NUM_LIT:0>:<EOL><INDENT>different = -m<EOL>for i in range(len(arr)):<EOL><INDENT>arr[i] += -m<EOL><DEDENT><DEDENT>k = max(arr)<EOL>temp_arr = [<NUM_LIT:0>] * (k + <NUM_LIT:1>)<EOL>for i in range(<NUM_LIT:0>, len(arr)):<EOL><INDENT>temp_arr[arr[i]] = temp_arr[arr[i]] + <NUM_LIT:1><EOL><DEDENT>for i in range(<NUM_LIT:1>, k + <NUM_LIT:1>):<EOL><INDENT>temp_arr[i] = temp_arr[i] + temp_arr[i - <NUM_LIT:1>]<EOL><DEDENT>result_arr = arr.copy()<EOL>for i in range(len(arr) - <NUM_LIT:1>, -<NUM_LIT:1>, -<NUM_LIT:1>):<EOL><INDENT>result_arr[temp_arr[arr[i]] - <NUM_LIT:1>] = arr[i] - different<EOL>temp_arr[arr[i]] = temp_arr[arr[i]] - <NUM_LIT:1><EOL><DEDENT>return result_arr<EOL>
Counting_sort
Sorting a array which has no element greater than k
Creating a new temp_arr,where temp_arr[i] contain the number of
element less than or equal to i in the arr
Then placing the number i into a correct position in the result_arr
return the result_arr
Complexity: 0(n)