Example usage

In the previous article, we explored optimizations for merge sort and quicksort—algorithms that perform exceptionally well in most scenarios. However, under certain specific conditions, alternative sorting algorithms may be required to meet particular requirements. This article delves into two advanced non-comparative sorting algorithms: bucket sort and radix sort, analyzing their underlying principles, implementation details, and respective application scenarios.

Bucket Sort

Principle

Bucket sort is a distribution-based sorting algorithm particularly effective when input data is uniformly distributed across a known range. Its core idea is to distribute elements into a finite number of buckets, sort each bucket individually (often using another sorting algorithm), and then concatenate the contents of all buckets in order.

Steps

1. Create buckets: Construct n buckets based on the value range of the input array.
2. Distribute elements: Iterate through the input array and place each element into its corresponding bucket.
3. Sort within buckets: Apply an auxiliary sorting algorithm (e.g., insertion sort or quicksort) to each non-empty bucket.
4. Concatenate buckets: Merge the sorted contents of all buckets sequentially to produce the final sorted result.

Code Example

Below is a Python implementation of bucket sort:

def bucket_sort(array):
    if len(array) == 0:
        return array

    # 1. Create buckets
    min_value = min(array)
    max_value = max(array)
    bucket_count = max_value - min_value + 1
    buckets = [[] for _ in range(bucket_count)]

    # 2. Distribute elements
    for num in array:
        buckets[num - min_value].append(num)

    # 3. Sort each bucket and concatenate
    sorted_array = []
    for bucket in buckets:
        if bucket:
            sorted_array.extend(sorted(bucket))  # Using Python's built-in sorted()

    return sorted_array

# Example usage
data = [3, 6, 2, 8, 4, 5, 7, 1]
print(bucket_sort(data))

Applicability

Bucket sort performs well under the following conditions:

• The input values fall within a relatively small, bounded integer range and are approximately uniformly distributed.
• When many duplicate values are present, bucket sort often outperforms comparison-based algorithms.

However, bucket sort has notable limitations: its efficiency heavily depends on both the choice of bucket count and the actual distribution of input data—making it sensitive to environmental assumptions.

Radix Sort

Principle

Radix sort is a non-comparative integer sorting algorithm that sorts numbers digit-by-digit. It processes digits either from the least significant digit (LSD) or the most significant digit (MSD), repeatedly applying a stable sub-sorting method (commonly counting sort or bucket sort) at each digit position.

Steps

1. Begin sorting from the least significant digit (or most significant digit).
2. Use a stable sorting subroutine (e.g., counting sort or bucket sort) to sort the array based on the current digit.
3. Repeat step 2 for each subsequent digit until all digits have been processed.

Code Example

Here is a Python implementation of radix sort using counting sort as the digit-wise subroutine:

def counting_sort_on_digit(array, exp):
    output = [0] * len(array)
    count = [0] * 10

    # Count frequency of each digit (0–9)
    for num in array:
        index = (num // exp) % 10
        count[index] += 1

    # Compute cumulative counts
    for i in range(1, 10):
        count[i] += count[i - 1]

    # Build output array in reverse order for stability
    for i in range(len(array) - 1, -1, -1):
        index = (array[i] // exp) % 10
        output[count[index] - 1] = array[i]
        count[index] -= 1

    return output

def radix_sort(array):
    if not array:
        return array

    max_value = max(array)
    exp = 1  # Start with units place

    while max_value // exp > 0:
        array = counting_sort_on_digit(array, exp)
        exp *= 10

    return array

# Example usage
data = [170, 45, 75, 90, 802, 24, 2, 66]
print(radix_sort(data))

Applicability

Radix sort is especially suitable for:

• Sequences of non-negative integers with limited digit length or bounded magnitude.
• Scenarios requiring high-throughput sorting of large numeric datasets, where traditional comparison-based methods would incur higher asymptotic costs.

Summary

This article thoroughly examined bucket sort and radix sort, two powerful linear-time sorting algorithms rooted in distribution and digit decomposition rather than pairwise comparisons. Each excels in specialized contexts—bucket sort when data is uniformly scattered over a modest range, and radix sort when handling fixed-width integers efficiently.

Having covered their theoretical foundations and practical implementations, the next article will compare these and other advanced sorting techniques, guiding you through strategic selection criteria to match the optimal algorithm to your specific problem constraints.