Course contentsShow
← Computer Science
Lesson 794 of 2,87218. Sorting AlgorithmsFree lesson

Radix Sort: Implementation and Analysis

Implementing radix sort with counting sort as subroutine and analyzing O(d(n+k)) complexity.

Radix Sort: Implementation and Analysis

You'll learn how to implement radix sort using counting sort as a helper and understand its O(d(n+k)) time complexity.

The Core Idea

Radix sort processes digits one at a time, and for each digit, it needs a stable sorting algorithm. Counting sort is perfect for this! For each digit position (from least significant to most significant in LSD radix sort), we use counting sort to arrange elements based on that digit alone.

The overall time complexity is O(d(n+k)) where:

  • d = number of digits in the largest number
  • n = number of elements
  • k = range of digit values (0-9 for decimal, so k=10)

Implementation Pattern

def radix_sort(arr):
    # Find maximum to know how many digits
    max_val = max(arr)
    
    # Start with least significant digit (ones place)
    exp = 1
    while max_val // exp > 0:
        counting_sort_by_digit(arr, exp)
        exp *= 10  # Move to next digit

For each digit position, counting sort runs in O(n+k). We repeat this d times (once per digit), giving us O(d(n+k)) total.

Why This Works

Since counting sort is stable, when we sort by a more significant digit, elements with the same digit remain in order based on less significant digits we've already sorted. It's like sorting papers: first alphabetize by last letter, then by second-to-last, and so on—stability ensures previous orderings are preserved.

When Is It Efficient?

Radix sort shines when d is small (numbers have few digits) and n is large. For example, sorting a million 4-digit numbers: O(4(1,000,000+10)) ≈ O(4 million) operations—linear-like performance!

Key Takeaway: Radix sort implements digit-by-digit sorting using stable counting sort as a subroutine, achieving O(d(n+k)) time complexity—effectively linear when the number of digits is constant.