Counting Sort

The Tally has a million monsters to line up, weakest first. Every monster has a power level from 1 to k, and k is small: ten levels, a few thousand at most. A comparison sort needs about n log n comparisons, around 20 million for a million monsters. The Tally needs none.

Write sort_powers(powers: list[int], k: int) -> list[int] that returns a new list with the same power levels in ascending order. Don't change powers.

sort_powers([3, 1, 4, 1, 5, 9, 2, 6, 5, 3], 10)   # [1, 1, 2, 3, 3, 4, 5, 5, 6, 9]
sort_powers([2, 2, 1], 2)                          # [1, 2, 2]
sort_powers([7], 10)                               # [7]
sort_powers([], 5)                                 # []

• 0 <= len(powers) <= 10^6, 1 <= k <= 10^5, and every power is in 1..k.
• Sort without comparing monsters: don't call sorted, list.sort, heapq or bisect anywhere in your file. (The Python tests check for these.)
• Aim for O(n + k). The tests sort a million monsters, and an O(n log n) sort you write yourself is too slow in Python. Looping over the whole army once per level is O(n·k), which fails when k is large.