Shell Sort

Shell sort enhances insertion sort through strategic interval-based partitioning. The algorithm processes elements using progressively smaller gaps, enabling distant elements to move toward their correct positions faster than standard insertion sort. Initial gaps start at half the array length, halving in each subsequent pass until reaching a gap of one.

Consider sorting [35, 33, 42, 10, 14, 19, 27, 44]:

1. With gap=4: Sort sublists [35,14], [33,19], [42,27], [10,44] → [14,19,27,10,35,33,42,44]
2. With gap=2: Sort sublists [14,27,35,42] and [19,10,33,44] → [14,10,27,33,35,19,42,44]
3. With gap=1: Full insertion sort yields [10,14,19,27,33,35,42,44]

Each iteration increases overall orderliness without guaranteeing full subsequence sorting until the final pass.

def shell_sort(data):
    n = len(data)
    gap = n // 2
    while gap > 0:
        for i in range(gap, n):
            current = data[i]
            j = i
            while j >= gap and data[j - gap] > current:
                data[j] = data[j - gap]
                j -= gap
            data[j] = current
        gap //= 2
    return data

Counting Sort

Counting sort achieves linear time complexity O(n) for integer sorting within constrained ranges. It counts occurrences of each value in an auxiliary array, then reconstructs the sorted sequence by iterating through value frequencies. This method eliminates comparisons by leveraging direct value indexing.

Implementation requires prior knowledge of the maximum value. The algorithm first tallies frequencies, then overwrites the original array by placing values according to their cumulative counts.

def counting_sort(values, max_value=100):
    counts = [0] * (max_value + 1)
    for num in values:
        counts[num] += 1
    position = 0
    for value in range(max_value + 1):
        for _ in range(counts[value]):
            values[position] = value
            position += 1

Bucket Sort

Bucket sort optimizes space usage for large-value ranges by distributing elements into multiple buckets. Each bucket represents a value subrange, with elements inserted in sorted order during distribution. The algorithm's efficiency depends heavily on input distribution uniformity.

During processing, each element is assigned to a bucket based on value proportionality. Elements are inserted into buckets using linear search for position, maintaining sorted order within each bucket before final concatenation.

def bucket_sort(elements, bucket_count=100, max_element=10000):
    buckets = [[] for _ in range(bucket_count)]
    for num in elements:
        index = min(num * bucket_count // (max_element + 1), bucket_count - 1)
        bucket = buckets[index]
        pos = len(bucket)
        while pos > 0 and bucket[pos - 1] > num:
            pos -= 1
        bucket.insert(pos, num)
    return [item for sublist in buckets for item in sublist]

Radix Sort

Radix sort processes integers digit by digit using stable bucket sorting. Starting from the least significant digit, it groups numbers by each digit position through successive bucket distributions. This approach maintains relative order of equal digits, ensuring stability across passes.

The algorithm determines digit positions from the maximum value. Each iteration processes one digit place, redistributing numbers into buckets before reassembling the sequence. Complexity scales linearly with both element count and digit length.

def radix_sort(integers):
    if not integers:
        return integers
    max_num = max(integers)
    digit_length = len(str(max_num))
    for position in range(digit_length):
        bins = [[] for _ in range(10)]
        for num in integers:
            digit = (num // (10 ** position)) % 10
            bins[digit].append(num)
        integers = [val for bin in bins for val in bin]
    return integers