Counting Sort Algorithm in DSA Go

Mental Model

Counting sort counts how many times each number appears, then uses these counts to place numbers in order without comparing them.

Analogy: Imagine sorting colored balls by counting how many balls of each color you have, then lining them up color by color based on those counts.

Input array: [4, 2, 2, 8, 3, 3, 1]
Count array: [0, 1, 2, 2, 1, 0, 0, 0, 1]
Sorted output: [1, 2, 2, 3, 3, 4, 8]

Dry Run Walkthrough

Input: array: [4, 2, 2, 8, 3, 3, 1]

Goal: Sort the array in ascending order using counting sort

Step 1: Find the maximum value to know count array size

Input: [4, 2, 2, 8, 3, 3, 1]
Max value: 8

Why: We need to know how big the count array should be to cover all numbers

Step 2: Create count array of size max+1 and initialize with zeros

Count array: [0, 0, 0, 0, 0, 0, 0, 0, 0]

Why: Count array holds how many times each number appears

Step 3: Count each number's frequency in input

Count array after counting: [0, 1, 2, 2, 1, 0, 0, 0, 1]

Why: Counting frequency helps us know how many times to place each number

Step 4: Modify count array to hold cumulative counts

Cumulative count array: [0, 1, 3, 5, 6, 6, 6, 6, 7]

Why: Cumulative counts tell the position of each number in the sorted output

Step 5: Place each element from input into output array using count array

Output array after placing: [1, 2, 2, 3, 3, 4, 8]

Why: Using counts to place elements ensures sorted order without comparisons

Result:

Sorted array: [1, 2, 2, 3, 3, 4, 8]

Annotated Code

DSA Go

package main

import "fmt"

func countingSort(arr []int) []int {
	if len(arr) == 0 {
		return arr
	}

	// Find max value to size count array
	max := arr[0]
	for _, val := range arr {
		if val > max {
			max = val
		}
	}

	// Create count array
	count := make([]int, max+1)

	// Count frequency of each number
	for _, val := range arr {
		count[val]++
	}

	// Modify count array to cumulative counts
	for i := 1; i <= max; i++ {
		count[i] += count[i-1]
	}

	// Create output array
	output := make([]int, len(arr))

	// Place elements in output using count array
	for i := len(arr) - 1; i >= 0; i-- {
		val := arr[i]
		count[val]--
		output[count[val]] = val
	}

	return output
}

func main() {
	arr := []int{4, 2, 2, 8, 3, 3, 1}
	sorted := countingSort(arr)
	for i, val := range sorted {
		if i == len(sorted)-1 {
			fmt.Printf("%d\n", val)
		} else {
			fmt.Printf("%d, ", val)
		}
	}
}

for _, val := range arr { if val > max { max = val } }

Find maximum value to size count array

for _, val := range arr { count[val]++ }

Count frequency of each number

for i := 1; i <= max; i++ { count[i] += count[i-1] }

Convert counts to cumulative counts for positions

for i := len(arr) - 1; i >= 0; i-- { val := arr[i]; count[val]--; output[count[val]] = val }

Place elements in output array in sorted order using counts

Output

1, 2, 2, 3, 3, 4, 8

Complexity Analysis

Time: O(n + k) because we count frequencies in O(n) and process count array of size k (max value)

Space: O(n + k) because we use output array of size n and count array of size k

vs Alternative: Counting sort is faster than comparison sorts (O(n log n)) when k (max value) is not much larger than n

Edge Cases

empty array

returns empty array immediately without error

DSA Go

if len(arr) == 0 { return arr }

array with one element

returns the same single-element array

DSA Go

function handles normally without special case

array with all elements the same

count array counts one value, output array is same as input

DSA Go

count[val]++ counts frequency correctly

When to Use This Pattern

When you need to sort integers with a known small range quickly and without comparisons, reach for counting sort because it uses counting and positions instead of comparing elements.

Common Mistakes

Mistake: Not converting count array to cumulative counts before placing elements
Fix: Add loop to convert counts to cumulative counts to know correct positions

Mistake: Placing elements in output array from start to end, causing unstable sort
Fix: Place elements from end to start to maintain stability

Summary

Counting sort sorts integers by counting their occurrences and placing them using cumulative counts.

Use it when sorting integers with a limited range efficiently and stably.

The key insight is using counts to find exact positions without comparing elements.