Radix Sort Algorithm in DSA Go

Mental Model

Radix sort sorts numbers by processing digits from least to most significant, grouping numbers by each digit step by step.

Analogy: Imagine sorting mail by zip code: first by the last digit, then the second last, and so on, until fully sorted.

Unsorted array:
[170, 45, 75, 90, 802, 24, 2, 66]

Buckets for digit 0-9:
0: []
1: []
2: []
3: []
4: []
5: []
6: []
7: []
8: []
9: []

Dry Run Walkthrough

Input: array: [170, 45, 75, 90, 802, 24, 2, 66]

Goal: Sort the array in ascending order using radix sort

Step 1: Sort numbers by least significant digit (units place)

Buckets:
0: [170, 90]
1: []
2: [802, 2]
3: []
4: [24]
5: [45, 75]
6: [66]
7: []
8: []
9: []
Reassembled array: [170, 90, 802, 2, 24, 45, 75, 66]

Why: Grouping by units digit arranges numbers partially by their last digit

Step 2: Sort numbers by second least significant digit (tens place)

Buckets:
0: [802, 2]
1: []
2: [24]
3: []
4: [45]
5: []
6: [66]
7: [170, 75]
8: []
9: [90]
Reassembled array: [802, 2, 24, 45, 66, 170, 75, 90]

Why: Grouping by tens digit refines order based on second digit

Step 3: Sort numbers by third least significant digit (hundreds place)

Buckets:
0: [2, 24, 45, 66, 75, 90]
1: [170]
2: []
3: []
4: []
5: []
6: []
7: []
8: [802]
9: []
Reassembled array: [2, 24, 45, 66, 75, 90, 170, 802]

Why: Grouping by hundreds digit completes sorting by most significant digit

Result:

Sorted array: [2, 24, 45, 66, 75, 90, 170, 802]

Annotated Code

DSA Go

package main

import (
	"fmt"
)

func getMax(arr []int) int {
	max := arr[0]
	for _, v := range arr {
		if v > max {
			max = v
		}
	}
	return max
}

func countingSort(arr []int, exp int) {
	output := make([]int, len(arr))
	count := make([]int, 10)

	// Count occurrences of digits
	for _, num := range arr {
		digit := (num / exp) % 10
		count[digit]++
	}

	// Change count[i] so it contains actual position
	for i := 1; i < 10; i++ {
		count[i] += count[i-1]
	}

	// Build output array from right to left to maintain stability
	for i := len(arr) - 1; i >= 0; i-- {
		digit := (arr[i] / exp) % 10
		count[digit]--
		output[count[digit]] = arr[i]
	}

	// Copy output to arr
	for i := 0; i < len(arr); i++ {
		arr[i] = output[i]
	}
}

func radixSort(arr []int) {
	if len(arr) == 0 {
		return
	}
	max := getMax(arr)

	// Sort by each digit
	for exp := 1; max/exp > 0; exp *= 10 {
		countingSort(arr, exp)
	}
}

func main() {
	arr := []int{170, 45, 75, 90, 802, 24, 2, 66}
	radixSort(arr)
	for i, v := range arr {
		if i > 0 {
			fmt.Print(", ")
		}
		fmt.Print(v)
	}
	fmt.Println()
}

for _, num := range arr { digit := (num / exp) % 10 count[digit]++ }

count occurrences of current digit for all numbers

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

transform count to positions for stable sorting

for i := len(arr) - 1; i >= 0; i-- { digit := (arr[i] / exp) % 10 count[digit]-- output[count[digit]] = arr[i] }

build output array from right to left to keep order stable

for i := 0; i < len(arr); i++ { arr[i] = output[i] }

copy sorted output back to original array

for exp := 1; max/exp > 0; exp *= 10 { countingSort(arr, exp) }

iterate over each digit place from least to most significant

Output

2, 24, 45, 66, 75, 90, 170, 802

Complexity Analysis

Time: O(d * (n + k)) where d is number of digits, n is number of elements, k is digit range (10); because we sort by each digit using counting sort

Space: O(n + k) for output and count arrays used in counting sort

vs Alternative: Compared to comparison sorts like quicksort O(n log n), radix sort can be faster for fixed digit size numbers because it sorts in linear time relative to input size

Edge Cases

empty array

function returns immediately without error

DSA Go

if len(arr) == 0 { return } // handle empty array before proceeding

array with one element

array remains unchanged as it is already sorted

DSA Go

for exp := 1; max/exp > 0; exp *= 10 { countingSort(arr, exp) } // loop runs but sorting one element is trivial

array with duplicate numbers

duplicates remain in correct sorted order due to stable counting sort

DSA Go

for i := len(arr) - 1; i >= 0; i-- { ... } // stable output preserves duplicates order

When to Use This Pattern

When you need to sort integers or fixed-length strings efficiently without comparisons, reach for radix sort because it sorts by digit positions in linear time.

Common Mistakes

Mistake: Not using stable sorting for each digit causes incorrect final order
Fix: Use counting sort from right to left to maintain stability for each digit pass

Mistake: Forgetting to process all digit places up to the max number's highest digit
Fix: Loop over digits until max/exp is zero to cover all digit places

Summary

Radix sort sorts numbers by processing digits from least to most significant using stable counting sort.

Use it when sorting integers or fixed-length data where comparison-based sorting is slower.

The key insight is sorting by each digit step-by-step preserves order and achieves full sorting efficiently.