Counting Sort

Sort a list of non-negative integers efficiently using counting sort.

sorting counting arrays

Implement the function `counting_sort(arr)` that takes a list of non-negative integers and returns a new list sorted in ascending order using the counting sort algorithm. The input list must not be modified. The algorithm should run in O(n + k) time and O(k) extra space, where n is the length of the list and k is the maximum value in the list plus one. If the list is empty, return an empty list.

Constraints

0 <= len(arr) <= 10^5
0 <= arr[i] <= 10^5
Values are non-negative integers.

Example

>>> counting_sort([3, 1, 2])
[1, 2, 3]
>>> counting_sort([4, 4, 0, 1, 0])
[0, 0, 1, 4, 4]
>>> counting_sort([])
[]

10 points ~15 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Find the maximum value in the array to determine the count array size.

Count occurrences of each value, then compute prefix sums to place elements correctly.

Build the output list by iterating through the original array from right to left for stability, or simply expand the counts.

For an empty array, return an empty list immediately.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.