Editor

Python Program for Counting Sort

Intermediate · Searching and sorting

Counting sort sorts whole numbers without comparing them with each other. It counts how many times each value appears, then writes the values out in order, each as many times as it was counted. It is very fast when the numbers fall in a small range, such as marks out of 10 or ages.

Program

counting_sort.py
numbers = [4, 2, 2, 8, 3, 3, 1, 0, 8]
print("Original list:", numbers)
# Count how many times each value from 0 to the largest appears
largest = max(numbers)
counts = [0] * (largest + 1)
for num in numbers:
counts[num] += 1
print(f"Counts for the values 0 to {largest}:", counts)
# Write each value out as many times as it was counted
sorted_list = []
for value in range(len(counts)):
for _ in range(counts[value]):
sorted_list.append(value)
print("Sorted list:", sorted_list)
Output
Original list: [4, 2, 2, 8, 3, 3, 1, 0, 8]
Counts for the values 0 to 8: [1, 1, 2, 2, 1, 0, 0, 0, 2]
Sorted list: [0, 1, 2, 2, 3, 3, 4, 8, 8]

How it works

  1. counts has one slot for every value from 0 to the largest number, all starting at 0.
  2. For each number, counts[num] += 1 adds one to its slot, so counts[2] ends up as 2 because 2 appears twice.
  3. The second loop goes through the values in order and appends each one counts[value] times.
  4. Values that never appear, like 5, 6 and 7, have a count of 0 and are skipped.
  5. This version only works for whole numbers 0 and above; the alternative handles negative numbers.

Another way to write it

Handling negative numbers

Handling negative numbers
numbers = [3, -2, 0, -2, 5, 1, -1]
low = min(numbers)
high = max(numbers)
counts = [0] * (high - low + 1)
for num in numbers:
counts[num - low] += 1 # shift so the smallest value uses slot 0
result = []
for i in range(len(counts)):
result.extend([i + low] * counts[i]) # shift back when writing out
print("Sorted list:", result)
Output
Sorted list: [-2, -2, -1, 0, 1, 3, 5]

Subtracting the smallest value moves every number into the range 0 and up, so -2 uses slot 0, and adding it back restores the real value.

Try it yourself

Sort the marks [7, 9, 7, 10, 4, 9, 7, 6] out of 10 with the main program and check which mark is the most common.

Edit the program above and press Run, or open it in the full editor to save it and share it. To watch it run line by line, open it in the visualizer.

Related programs

All Python programs · CBSE class 12 practical file · Python exercises