Counting Sort - Algorithm, Visualization, Examples

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

    # Store count of each element
    for num in arr:
        count[num - min_val] += 1

    # Change count[i] so that count[i] now contains actual position
    for i in range(1, len(count)):
        count[i] += count[i - 1]

    # Build the output array
    for num in reversed(arr):
        output[count[num - min_val] - 1] = num
        count[num - min_val] -= 1

    return output

if __name__ == '__main__':
    arr = [6, 3, 8, 2, 7, 4]
    sorted_arr = counting_sort(arr)
    print("Sorted array is:", sorted_arr)