Counting Sort and Radix Sort

Overview

Counting Sort and Radix Sort represent a class of sorting algorithms that break the O(n log n) lower bound of comparison-based sorting by making assumptions about the input data. These algorithms operate on integer keys or data that can be represented as integers, achieving linear time complexity under specific conditions.

Counting Sort works by counting the number of occurrences of each distinct element, then using arithmetic to determine the position of each element in the sorted output. The algorithm requires knowledge of the range of input values and allocates auxiliary space proportional to this range.

Radix Sort processes integers digit by digit, using a stable sorting algorithm (typically Counting Sort) as a subroutine. By sorting from the least significant digit to the most significant digit, or vice versa, Radix Sort achieves linear time complexity relative to the number of digits.

Both algorithms emerged from the need to sort large datasets efficiently when data characteristics are known. Counting Sort traces back to Harold Seward's work in the 1950s on sorting punch cards. Radix Sort has even earlier origins in mechanical sorting machines used for tabulating census data.

The primary advantage of these algorithms is performance on suitable datasets. Counting Sort runs in O(n + k) time where k is the range of input values. Radix Sort runs in O(d * (n + k)) where d is the number of digits. When k and d are small relative to n, these algorithms significantly outperform comparison-based alternatives.

# Counting Sort example with small range
data = [4, 2, 2, 8, 3, 3, 1]
max_val = 8

# Count occurrences
counts = Array.new(max_val + 1, 0)
data.each { |num| counts[num] += 1 }

# Build sorted array
sorted = []
counts.each_with_index do |count, num|
  count.times { sorted << num }
end

sorted
# => [1, 2, 2, 3, 3, 4, 8]

Key Principles

Counting Sort operates on three fundamental steps: counting, accumulation, and placement. The counting phase creates a histogram of the input data, tallying how many times each value appears. The accumulation phase transforms these counts into positions by computing prefix sums. The placement phase iterates through the input in reverse order, using the accumulated counts to place each element in its correct position.

The algorithm requires that input values fall within a known range [min, max]. The auxiliary space requirements scale with the range k = max - min + 1, not with the number of elements n. This creates a critical trade-off: Counting Sort excels when k = O(n) but becomes impractical when k >> n.

Stability is a defining characteristic of Counting Sort implementations. A sorting algorithm is stable if it preserves the relative order of elements with equal keys. Stability matters when sorting composite objects by one field while maintaining the order established by previous sorts. The reverse iteration during placement ensures stability by placing equal elements in their original relative order.

# Demonstrating stability with composite objects
Person = Struct.new(:name, :age)
people = [
  Person.new("Alice", 30),
  Person.new("Bob", 25),
  Person.new("Charlie", 30)
]

# Stable sort by age preserves Alice before Charlie (both age 30)
def counting_sort_by_age(people)
  min_age = people.map(&:age).min
  max_age = people.map(&:age).max
  range = max_age - min_age + 1
  
  counts = Array.new(range, 0)
  people.each { |p| counts[p.age - min_age] += 1 }
  
  # Prefix sum
  (1...range).each { |i| counts[i] += counts[i - 1] }
  
  output = Array.new(people.length)
  (people.length - 1).downto(0) do |i|
    age_index = people[i].age - min_age
    output[counts[age_index] - 1] = people[i]
    counts[age_index] -= 1
  end
  
  output
end

Radix Sort builds upon Counting Sort by processing multi-digit numbers one digit at a time. The algorithm partitions the sorting problem into d independent sorts, where d is the number of digits. Each digit-level sort must be stable to ensure correctness.

Two variants exist: Least Significant Digit (LSD) and Most Significant Digit (MSD). LSD Radix Sort processes digits from right to left, sorting by the ones place, then tens place, then hundreds place, and so on. This approach works because stable sorting by digit d preserves the order established by sorting digits 0 through d-1.

MSD Radix Sort processes digits from left to right, creating a recursive partitioning similar to quicksort. After sorting by the most significant digit, the algorithm recursively sorts each bucket by remaining digits. MSD can terminate early for buckets containing identical prefixes, providing performance advantages on certain datasets.

The choice of radix (base) affects performance. Binary (base 2) requires d = log₂(max) passes, while base 256 requires d = log₂₅₆(max) passes. Larger radices reduce the number of passes but increase the auxiliary space and cache misses per pass. Base 10 provides intuitive debugging, while base 256 aligns with byte boundaries in binary data.

# LSD Radix Sort processing digits right to left
def radix_sort_lsd(array)
  return array if array.empty?
  
  max_val = array.max
  exp = 1
  
  while max_val / exp > 0
    array = counting_sort_by_digit(array, exp)
    exp *= 10
  end
  
  array
end

def counting_sort_by_digit(array, exp)
  output = Array.new(array.length)
  counts = Array.new(10, 0)
  
  # Count digit occurrences
  array.each do |num|
    digit = (num / exp) % 10
    counts[digit] += 1
  end
  
  # Prefix sum
  (1...10).each { |i| counts[i] += counts[i - 1] }
  
  # Build output (reverse for stability)
  (array.length - 1).downto(0) do |i|
    digit = (array[i] / exp) % 10
    output[counts[digit] - 1] = array[i]
    counts[digit] -= 1
  end
  
  output
end

Ruby Implementation

Ruby provides the necessary array manipulation and arithmetic operations to implement both algorithms efficiently. The standard library does not include Counting Sort or Radix Sort, as the built-in sort method uses a hybrid algorithm (Timsort) optimized for general-purpose sorting.

A complete Counting Sort implementation must handle negative numbers by shifting the range. The algorithm determines the minimum and maximum values, creates a count array sized to the range, and offsets all indices by the minimum value.

def counting_sort(array)
  return [] if array.empty?
  
  min_val = array.min
  max_val = array.max
  range = max_val - min_val + 1
  
  # Count occurrences
  counts = Array.new(range, 0)
  array.each { |num| counts[num - min_val] += 1 }
  
  # Transform counts to positions (prefix sum)
  (1...range).each { |i| counts[i] += counts[i - 1] }
  
  # Place elements (reverse iteration for stability)
  output = Array.new(array.length)
  (array.length - 1).downto(0) do |i|
    index = array[i] - min_val
    output[counts[index] - 1] = array[i]
    counts[index] -= 1
  end
  
  output
end

# Example with negative numbers
data = [5, -1, 3, -1, 0, 2]
counting_sort(data)
# => [-1, -1, 0, 2, 3, 5]

For sorting objects by a numeric key, the implementation extracts keys, tracks original objects, and rebuilds the sorted array. This pattern appears frequently when sorting database records or structured data.

def counting_sort_by(array, &key_extractor)
  return [] if array.empty?
  
  keys = array.map(&key_extractor)
  min_key = keys.min
  max_key = keys.max
  range = max_key - min_key + 1
  
  counts = Array.new(range, 0)
  keys.each { |key| counts[key - min_key] += 1 }
  
  (1...range).each { |i| counts[i] += counts[i - 1] }
  
  output = Array.new(array.length)
  (array.length - 1).downto(0) do |i|
    key = keys[i]
    index = key - min_key
    output[counts[index] - 1] = array[i]
    counts[index] -= 1
  end
  
  output
end

# Sort strings by length
words = ["cat", "be", "apple", "dog", "at"]
counting_sort_by(words, &:length)
# => ["be", "at", "cat", "dog", "apple"]

Radix Sort in Ruby requires careful digit extraction and base selection. The implementation uses integer division and modulo operations to isolate individual digits. For base 10, digit extraction uses (num / 10^position) % 10.

def radix_sort(array, base: 10)
  return array if array.empty?
  
  max_val = array.max
  exp = 1
  
  while max_val / exp > 0
    array = counting_sort_by_digit(array, exp, base)
    exp *= base
  end
  
  array
end

def counting_sort_by_digit(array, exp, base)
  output = Array.new(array.length)
  counts = Array.new(base, 0)
  
  array.each do |num|
    digit = (num / exp) % base
    counts[digit] += 1
  end
  
  (1...base).each { |i| counts[i] += counts[i - 1] }
  
  (array.length - 1).downto(0) do |i|
    digit = (array[i] / exp) % base
    output[counts[digit] - 1] = array[i]
    counts[digit] -= 1
  end
  
  output
end

# Example with different bases
data = [170, 45, 75, 90, 802, 24, 2, 66]
radix_sort(data, base: 10)
# => [2, 24, 45, 66, 75, 90, 170, 802]

radix_sort(data, base: 16)  # Hexadecimal
# => [2, 24, 45, 66, 75, 90, 170, 802]

Handling negative numbers in Radix Sort requires splitting the array into negative and positive partitions, sorting each separately, and concatenating the results. The negative partition sorts by absolute value in descending order.

def radix_sort_with_negatives(array)
  return array if array.empty?
  
  negatives = array.select { |n| n < 0 }.map(&:-@)
  positives = array.select { |n| n >= 0 }
  
  sorted_negatives = radix_sort(negatives).reverse.map(&:-@)
  sorted_positives = radix_sort(positives)
  
  sorted_negatives + sorted_positives
end

data = [170, -45, 75, -90, 24, -2, 66]
radix_sort_with_negatives(data)
# => [-90, -45, -2, 24, 66, 75, 170]

MSD Radix Sort implementation in Ruby uses recursion to process buckets independently. The algorithm partitions by the current digit, then recursively sorts each non-empty bucket by remaining digits.

def radix_sort_msd(array, base: 10)
  return array if array.length <= 1
  
  max_val = array.max
  max_digits = Math.log(max_val, base).floor + 1
  
  msd_sort_recursive(array, 0, array.length, max_digits - 1, base)
end

def msd_sort_recursive(array, start, length, digit, base)
  return array if length <= 1 || digit < 0
  
  exp = base ** digit
  counts = Array.new(base + 1, 0)
  
  # Count digit occurrences
  (start...start + length).each do |i|
    d = (array[i] / exp) % base
    counts[d + 1] += 1
  end
  
  # Prefix sum
  (0...base).each { |i| counts[i + 1] += counts[i] }
  
  # Rearrange elements
  temp = Array.new(length)
  (start...start + length).each do |i|
    d = (array[i] / exp) % base
    temp[counts[d]] = array[i]
    counts[d] += 1
  end
  
  # Copy back
  temp.each_with_index do |val, i|
    array[start + i] = val
  end
  
  # Recursively sort buckets
  (0...base).each do |d|
    bucket_start = start + counts[d]
    bucket_length = counts[d + 1] - counts[d]
    msd_sort_recursive(array, bucket_start, bucket_length, digit - 1, base)
  end
  
  array
end

Practical Examples

Counting Sort excels when sorting ages in a demographic database. Ages typically range from 0 to 120, providing a small constant range regardless of dataset size.

class Demographics
  def self.sort_by_age(people)
    return [] if people.empty?
    
    # Ages range from 0 to 120
    MAX_AGE = 120
    counts = Array.new(MAX_AGE + 1, 0)
    
    people.each { |person| counts[person[:age]] += 1 }
    (1..MAX_AGE).each { |i| counts[i] += counts[i - 1] }
    
    output = Array.new(people.length)
    (people.length - 1).downto(0) do |i|
      age = people[i][:age]
      output[counts[age] - 1] = people[i]
      counts[age] -= 1
    end
    
    output
  end
end

people = [
  { name: "Alice", age: 34 },
  { name: "Bob", age: 25 },
  { name: "Charlie", age: 34 },
  { name: "Diana", age: 25 }
]

Demographics.sort_by_age(people)
# => [
#   { name: "Bob", age: 25 },
#   { name: "Diana", age: 25 },
#   { name: "Alice", age: 34 },
#   { name: "Charlie", age: 34 }
# ]

Radix Sort handles sorting IP addresses represented as 32-bit integers. Each octet (8 bits) forms a digit in base 256, requiring exactly four passes.

class IPSorter
  def self.ip_to_int(ip)
    octets = ip.split('.').map(&:to_i)
    (octets[0] << 24) + (octets[1] << 16) + (octets[2] << 8) + octets[3]
  end
  
  def self.int_to_ip(num)
    [
      (num >> 24) & 0xFF,
      (num >> 16) & 0xFF,
      (num >> 8) & 0xFF,
      num & 0xFF
    ].join('.')
  end
  
  def self.sort(ip_addresses)
    integers = ip_addresses.map { |ip| ip_to_int(ip) }
    
    # Radix sort with base 256 (one byte at a time)
    4.times do |pass|
      shift = pass * 8
      integers = counting_sort_byte(integers, shift)
    end
    
    integers.map { |num| int_to_ip(num) }
  end
  
  def self.counting_sort_byte(array, shift)
    counts = Array.new(256, 0)
    
    array.each do |num|
      byte = (num >> shift) & 0xFF
      counts[byte] += 1
    end
    
    (1...256).each { |i| counts[i] += counts[i - 1] }
    
    output = Array.new(array.length)
    (array.length - 1).downto(0) do |i|
      byte = (array[i] >> shift) & 0xFF
      output[counts[byte] - 1] = array[i]
      counts[byte] -= 1
    end
    
    output
  end
end

ips = ["192.168.1.10", "10.0.0.1", "192.168.1.5", "172.16.0.1"]
IPSorter.sort(ips)
# => ["10.0.0.1", "172.16.0.1", "192.168.1.5", "192.168.1.10"]

Bucket sort combined with Radix Sort handles floating-point numbers by separating them into buckets based on integer parts, then using Radix Sort within each bucket.

def bucket_radix_sort(floats, num_buckets: 10)
  return floats if floats.empty?
  
  min_val = floats.min
  max_val = floats.max
  range = max_val - min_val
  bucket_size = range / num_buckets
  
  buckets = Array.new(num_buckets) { [] }
  
  # Distribute into buckets
  floats.each do |num|
    index = ((num - min_val) / bucket_size).floor
    index = num_buckets - 1 if index >= num_buckets
    buckets[index] << num
  end
  
  # Sort each bucket and concatenate
  buckets.flat_map do |bucket|
    next [] if bucket.empty?
    
    # Convert to integers, sort, convert back
    scale = 1000
    integers = bucket.map { |f| (f * scale).round }
    sorted_ints = radix_sort(integers)
    sorted_ints.map { |i| i / scale.to_f }
  end
end

data = [0.897, 0.565, 0.656, 0.123, 0.665, 0.343]
bucket_radix_sort(data)
# => [0.123, 0.343, 0.565, 0.656, 0.665, 0.897]

Sorting dates efficiently uses Counting Sort on a composite key formed from year, month, and day components.

require 'date'

class DateSorter
  def self.sort_dates(date_strings)
    dates = date_strings.map { |ds| Date.parse(ds) }
    
    # Convert to sortable integer: YYYYMMDD
    date_keys = dates.map do |d|
      d.year * 10000 + d.month * 100 + d.day
    end
    
    sorted_keys = radix_sort(date_keys)
    
    # Convert back to dates
    sorted_keys.map do |key|
      year = key / 10000
      month = (key / 100) % 100
      day = key % 100
      Date.new(year, month, day).to_s
    end
  end
end

dates = ["2024-03-15", "2023-12-01", "2024-01-20", "2023-12-15"]
DateSorter.sort_dates(dates)
# => ["2023-12-01", "2023-12-15", "2024-01-20", "2024-03-15"]

Performance Considerations

Counting Sort achieves O(n + k) time complexity where n is the number of elements and k is the range of values. The algorithm makes exactly one pass to count elements, one pass to compute prefix sums, and one pass to place elements. The space complexity is O(n + k) for the output array and count array.

The performance degrades when k >> n. Sorting one million random integers between 0 and one billion requires a count array with one billion entries, consuming gigabytes of memory. This makes Counting Sort impractical despite its theoretical linear time.

The constant factors in Counting Sort are small. The algorithm performs simple arithmetic operations (incrementing, array access) without comparisons or swaps. Cache performance suffers when the count array exceeds cache size, as the counting phase exhibits poor spatial locality.

require 'benchmark'

def compare_sorting_methods(size, range)
  data = Array.new(size) { rand(range) }
  
  Benchmark.bm(20) do |x|
    x.report("counting_sort") { counting_sort(data.dup) }
    x.report("radix_sort") { radix_sort(data.dup) }
    x.report("Array#sort") { data.dup.sort }
  end
end

# Small range - Counting Sort wins
compare_sorting_methods(100_000, 1000)
# counting_sort:  0.015s
# radix_sort:     0.025s
# Array#sort:     0.045s

# Large range - Counting Sort loses
compare_sorting_methods(100_000, 1_000_000)
# counting_sort:  0.850s (high memory)
# radix_sort:     0.035s
# Array#sort:     0.048s

Radix Sort achieves O(d * (n + b)) time complexity where d is the number of digits, n is the number of elements, and b is the base. For integers up to maximum value m, d = log_b(m). The space complexity is O(n + b) for the output array and count array used in each pass.

The choice of base creates a time-space trade-off. Base 2 minimizes space (count array of size 2) but maximizes passes (d = log₂(m)). Base 256 reduces passes (d = log₂₅₆(m)) but requires a count array of size 256. Base 10 provides a middle ground with intuitive debugging.

For 32-bit integers (m = 2³²), base 2 requires 32 passes, base 10 requires 10 passes, base 16 requires 8 passes, and base 256 requires 4 passes. Higher bases reduce the number of passes but increase the cost per pass due to larger count arrays and worse cache performance.

def analyze_radix_bases(data)
  bases = [2, 10, 16, 256]
  max_val = data.max
  
  bases.each do |base|
    digits = Math.log(max_val, base).ceil
    passes = digits
    count_array_size = base
    
    puts "Base #{base}: #{passes} passes, count array size #{count_array_size}"
  end
end

data = Array.new(100_000) { rand(2**32) }
analyze_radix_bases(data)
# Base 2: 32 passes, count array size 2
# Base 10: 10 passes, count array size 10
# Base 16: 8 passes, count array size 16
# Base 256: 4 passes, count array size 256

LSD Radix Sort must complete all d passes regardless of data distribution. MSD Radix Sort can terminate early when buckets contain uniform values, providing better average-case performance on certain datasets. However, MSD requires more complex bookkeeping and performs poorly on random data.

The stability overhead in Radix Sort comes from processing elements in reverse order during each counting sort pass. This adds complexity but ensures correctness. Non-stable radix sort implementations exist but lose the ability to sort composite objects correctly.

Memory access patterns significantly affect real-world performance. Counting Sort and Radix Sort perform sequential writes to the output array, providing good spatial locality. However, reading from the count array exhibits poor temporal locality when k or b is large, causing cache misses.

# Demonstrating cache effects with different ranges
def measure_cache_impact
  size = 1_000_000
  
  # Small range - fits in cache
  small_range = Array.new(size) { rand(100) }
  t1 = Time.now
  counting_sort(small_range)
  small_time = Time.now - t1
  
  # Large range - exceeds cache
  large_range = Array.new(size) { rand(100_000) }
  t2 = Time.now
  counting_sort(large_range)
  large_time = Time.now - t2
  
  puts "Small range (100): #{small_time}s"
  puts "Large range (100k): #{large_time}s"
  puts "Slowdown factor: #{(large_time / small_time).round(2)}x"
end

Common Pitfalls

Forgetting to handle negative numbers breaks Counting Sort. The algorithm assumes all indices are non-negative, causing errors when negative values appear in the input. Always determine the minimum value and shift the range accordingly.

# INCORRECT - fails with negative numbers
def counting_sort_broken(array)
  max_val = array.max
  counts = Array.new(max_val + 1, 0)
  array.each { |num| counts[num] += 1 }  # Error if num < 0
  # ...
end

# CORRECT - handles negative numbers
def counting_sort_correct(array)
  min_val = array.min
  max_val = array.max
  range = max_val - min_val + 1
  counts = Array.new(range, 0)
  array.each { |num| counts[num - min_val] += 1 }
  # ...
end

data = [5, -2, 3, -2, 0]
counting_sort_correct(data)
# => [-2, -2, 0, 3, 5]

Using forward iteration during the placement phase destroys stability. Elements with equal keys must maintain their relative order, which requires processing the input array in reverse.

# UNSTABLE - forward iteration
def counting_sort_unstable(array)
  # ... counting and prefix sum ...
  
  output = Array.new(array.length)
  array.each_with_index do |num, i|  # Forward iteration
    index = num - min_val
    output[counts[index] - 1] = num
    counts[index] -= 1
  end
  output
end

# STABLE - reverse iteration
def counting_sort_stable(array)
  # ... counting and prefix sum ...
  
  output = Array.new(array.length)
  (array.length - 1).downto(0) do |i|  # Reverse iteration
    index = array[i] - min_val
    output[counts[index] - 1] = array[i]
    counts[index] -= 1
  end
  output
end

Allocating excessive memory for the count array wastes resources. When sorting sparse data with a large range, most count array entries remain zero. Alternative data structures like hash tables can store only non-zero counts.

# Memory-efficient for sparse data
def counting_sort_sparse(array)
  return [] if array.empty?
  
  min_val = array.min
  counts = Hash.new(0)
  
  array.each { |num| counts[num] += 1 }
  
  sorted = []
  (min_val..array.max).each do |num|
    counts[num].times { sorted << num }
  end
  
  sorted
end

# Works efficiently even with large range
sparse_data = [1, 1000000, 2, 999999]
counting_sort_sparse(sparse_data)
# => [1, 2, 999999, 1000000]

Integer overflow occurs in Radix Sort when computing positions or extracting digits. Ruby handles arbitrary precision integers automatically, but conversion to floats or improper scaling can introduce errors.

# Potential overflow with float conversion
def radix_sort_risky(array)
  max_val = array.max.to_f  # Float loses precision for large integers
  # ...
end

# Safe with integer arithmetic
def radix_sort_safe(array)
  max_val = array.max  # Stays as arbitrary precision integer
  # ...
end

Choosing an inappropriate base for Radix Sort affects performance. Base 2 works for all integers but requires many passes. Very large bases (like 2¹⁶) reduce passes but create large count arrays that exceed cache size.

Off-by-one errors in digit extraction frequently cause incorrect results. The expression (num / exp) % base extracts a specific digit, but incorrect exponent calculation leads to wrong digits.

# Testing digit extraction
def test_digit_extraction(num, base)
  digits = []
  exp = 1
  while num / exp > 0
    digit = (num / exp) % base
    digits << digit
    exp *= base
  end
  digits
end

test_digit_extraction(12345, 10)
# => [5, 4, 3, 2, 1]  # Correct: least to most significant

Failing to preserve object references during sorting breaks when sorting arrays of mutable objects. The algorithm must move the actual objects, not copy their values.

# Demonstrates reference preservation
Person = Struct.new(:name, :score)
people = [
  Person.new("Alice", 85),
  Person.new("Bob", 92),
  Person.new("Charlie", 85)
]

sorted = counting_sort_by(people) { |p| p.score }

# Original objects preserved
sorted[0].name = "Modified"
puts people.find { |p| p.name == "Modified" }.score
# => 85 (same object reference)

Reference

Counting Sort Characteristics

Radix Sort Characteristics

Algorithm Selection Guide

Base Selection for Radix Sort

Common Operations

Space Requirements

Performance Thresholds