编辑代码

def counting_sort(arr):
    if not arr:
        return arr
    output = [0] * len(arr)
    count = [0] * (max(arr) + 1)

    for i in arr:
        count[i] += 1

    for i in range(1, len(count)):
        count[i] += count[i - 1]

    for i in range(len(arr) - 1, -1, -1):
        output[count[arr[i]] - 1] = arr[i]
        count[arr[i]] -= 1

    return output