Summary - Counting sort

Implement counting sort and print the result.

Summary - Counting sort

Counting sort: count + cumulative + place backward. Non-comparison, O(n + k), stable. k is the key range.

Fast on a small integer range; memory explodes on large ranges. Negative values need an offset.

Used as the sub-sorter in radix sort; this lets us sort larger numbers too.

Exercise Summary: counting sort

Write counting_sort(arr). Print [1, 2, 2, 4, 5, 8] with print(counting_sort([5,1,4,2,8,2])).

Show example solution

def counting_sort(arr):
    # Counting sort
    if not arr:
        return []
    k = max(arr) + 1
    count = [0] * k
    for x in arr:
        count[x] += 1
    for i in range(1, k):
        count[i] += count[i - 1]
    output = [0] * len(arr)
    for i in range(len(arr) - 1, -1, -1):
        output[count[arr[i]] - 1] = arr[i]
        count[arr[i]] -= 1
    return output
print(counting_sort([5, 1, 4, 2, 8, 2]))

Test yourself

Summary - Counting sort: match the terms

Cost

O(n+k)
Memory

O(k)
Stable

Yes
Range

Must be narrow

Cumulative

count[i] ____count[i-1]

Show answer

count[i] +=count[i-1]

Does counting sort compare elements?
- No
- Only on small arrays
- Only on large arrays
- Yes, always
Show answer

No — No

Next lesson: Radix idea

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies