(arr)
return result_arr
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)

    Examples:
    >>> counting_sort([0, 5, 3, 2, 2])
    [0, 2, 2, 3, 5]
    
    >>> counting_sort([-2, -5, -45])
    [-45, -5, -2]
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)
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 )
def counting_sort(arr):
    """
    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)

    Examples:
    >>> counting_sort([0, 5, 3, 2, 2])
    [0, 2, 2, 3, 5]
    
    >>> counting_sort([-2, -5, -45])
    [-45, -5, -2]
    """

    m = min(arr)
    # in case there are negative elements, change the array to all positive element
    different = 0
    if m < 0:
        # save the change, so that we can convert the array back to all positive number
        different = -m
        for i in range(len(arr)):
            arr[i] += -m
    k = max(arr)
    temp_arr = [0] * (k + 1)
    for i in range(0, len(arr)):
        temp_arr[arr[i]] = temp_arr[arr[i]] + 1
    # temp_array[i] contain the times the number i appear in arr

    for i in range(1, k + 1):
        temp_arr[i] = temp_arr[i] + temp_arr[i - 1]
    # temp_array[i] contain the number of element less than or equal i in arr

    result_arr = [0] * len(arr)
    # creating a result_arr an put the element in a correct positon
    for i in range(len(arr) - 1, -1, -1):
        result_arr[temp_arr[arr[i]] - 1] = arr[i] - different
        temp_arr[arr[i]] = temp_arr[arr[i]] - 1

    return result_arr
def counting_sort ( arr ) : m = min ( arr ) # in case there are negative elements, change the array to all positive element different = 0 if m < 0 : # save the change, so that we can convert the array back to all positive number different = - m for i in range ( len ( arr ) ) : arr [ i ] += - m k = max ( arr ) temp_arr = [ 0 ] * ( k + 1 ) for i in range ( 0 , len ( arr ) ) : temp_arr [ arr [ i ] ] = temp_arr [ arr [ i ] ] + 1 # temp_array[i] contain the times the number i appear in arr for i in range ( 1 , k + 1 ) : temp_arr [ i ] = temp_arr [ i ] + temp_arr [ i - 1 ] # temp_array[i] contain the number of element less than or equal i in arr result_arr = [ 0 ] * len ( arr ) # creating a result_arr an put the element in a correct positon for i in range ( len ( arr ) - 1 , - 1 , - 1 ) : result_arr [ temp_arr [ arr [ i ] ] - 1 ] = arr [ i ] - different temp_arr [ arr [ i ] ] = temp_arr [ arr [ i ] ] - 1 return result_arr