Home About Me

Four Sorting Algorithms, Four Very Different Trade-offs: Selection, Heap, Merge, and Radix Sort

2026-06-06

Sorting algorithms may all aim for the same result, but they get there in very different ways. Some rely on repeated selection, some on tree structures, some on divide-and-conquer, and some avoid direct comparisons entirely.

This section looks at four classic methods in detail: simple selection sort, heap sort, merge sort, and radix sort. Each one has a distinct idea behind it, along with clear strengths, weaknesses, and suitable use cases.

1. Simple Selection Sort

Core idea

Simple selection sort is built around a straightforward pattern: select, then swap.

Its logic follows a greedy approach. In each round, scan the unsorted portion of the array, find the minimum value (or maximum, if sorting in descending order), and swap it with the first element of that unsorted range. After one round, the unsorted range shrinks by one. Repeat until nothing remains unsorted.

The whole process is essentially a loop of:

  • find the minimum
  • swap it into position
  • reduce the unsorted range

This makes it a typical selection-based sorting algorithm.

How it runs

Using the test array [49, 38, 65, 97, 76, 13, 27, 49]:

  1. Initial unsorted range: [49, 38, 65, 97, 76, 13, 27, 49] (index 0 to 7) - The minimum is 13 at index 5. - Swap it with 49 at index 0. - Result: [13, 38, 65, 97, 76, 49, 27, 49]

  2. Remaining unsorted range: [38, 65, 97, 76, 49, 27, 49] (index 1 to 7) - The minimum is 27 at index 6. - Swap it with 38 at index 1. - Result: [13, 27, 65, 97, 76, 49, 38, 49]

  3. Remaining unsorted range: [65, 97, 76, 49, 38, 49] (index 2 to 7) - The minimum is 38 at index 6. - Swap it with 65 at index 2. - Result: [13, 27, 38, 97, 76, 49, 65, 49]

  4. Continue in the same way, shrinking the unsorted range after every round.

  5. Final sorted array: - [13, 27, 38, 49, 49, 65, 76, 97]

Python implementation

def selection_sort(arr):
    """
    简单选择排序（升序）
    :param arr: 待排序数组（列表）
    :return: 排序后的数组（不修改原数组）
    """
    arr_copy = arr.copy()
    n = len(arr_copy)
    # 外层循环：控制待排序区间的起始位置（0 ~ n-2）
    for i in range(n - 1):
        min_idx = i  # 初始化最小值索引为待排序区间第一个元素
        # 内层循环：遍历待排序区间，找到最小值索引
        for j in range(i + 1, n):
            if arr_copy[j] < arr_copy[min_idx]:
                min_idx = j
        # 交换最小值与待排序区间第一个元素
        arr_copy[i], arr_copy[min_idx] = arr_copy[min_idx], arr_copy[i]
    return arr_copy

# 优化版：二元选择排序（同时找最小/最大值，减少循环次数）
def selection_sort_optimized(arr):
    arr_copy = arr.copy()
    n = len(arr_copy)
    left = 0
    right = n - 1
    while left < right:
        min_idx = left
        max_idx = right
        # 一次遍历同时找最小、最大值索引
        for j in range(left, right + 1):
            if arr_copy[j] < arr_copy[min_idx]:
                min_idx = j
            if arr_copy[j] > arr_copy[max_idx]:
                max_idx = j
        # 交换最小值到左边界
        arr_copy[left], arr_copy[min_idx] = arr_copy[min_idx], arr_copy[left]
        # 若最大值索引是左边界（已被交换），更新最大值索引
        if max_idx == left:
            max_idx = min_idx
        # 交换最大值到右边界
        arr_copy[right], arr_copy[max_idx] = arr_copy[max_idx], arr_copy[right]
        # 缩小待排序区间
        left += 1
        right -= 1
    return arr_copy

# 测试用例
if __name__ == "__main__":
    test_arr = [49, 38, 65, 97, 76, 13, 27, 49]
    res1 = selection_sort(test_arr)
    res2 = selection_sort_optimized(test_arr)
    print("原始数组：", test_arr)
    print("基础版排序后：", res1)  # [13, 27, 38, 49, 49, 65, 76, 97]
    print("优化版排序后：", res2)  # [13, 27, 38, 49, 49, 65, 76, 97]

What matters in the code

Basic version

  • The outer loop i marks the beginning of the unsorted range.
  • The inner loop j scans from i + 1 to n - 1 to find the index of the minimum value.
  • That minimum is then swapped with arr[i], completing one round.

Optimized version: dual selection

  • It searches for both the minimum and maximum in a single pass.
  • That allows each round to place two elements instead of one, cutting the number of passes by roughly half.
  • One detail needs attention: if the maximum was originally at the left boundary, its index must be updated after the minimum swap.

Characteristics and possible optimizations

Advantages

  • Easy to understand and easy to implement.
  • Performs very few swaps, at most n - 1, which is better than bubble sort in that respect.

Disadvantages

  • It is not stable. For example, in [2, 1, 2], the first 2 may be swapped behind the second 2, changing their original order.
  • Its time complexity stays at O(n²) regardless of whether the array is already partly sorted.

Optimization ideas

  • Use dual selection sort to find both minimum and maximum at once.
  • Skip the region that is already known to be sorted.
  • For small datasets, it can be combined with insertion sort.

2. Heap Sort

Core idea

Heap sort is based on the heap, which is a complete binary tree structure. Its workflow can be summarized as:

  • build a heap
  • swap the heap top with the end
  • restore the heap

For ascending order, it typically uses a max-heap:

  • every parent node is greater than or equal to its children
  • the root is the largest element in the heap

Once the array is converted into a max-heap, the largest element sits at the top. Swap it with the last element, reduce the heap size, and then adjust the remaining elements back into heap order. Repeat until only one element remains.

How it runs

Using [49, 38, 65, 97, 76, 13, 27, 49]:

  1. Build a max-heap: - [97, 76, 65, 49, 38, 13, 27, 49] - 97 is now at the root.

  2. Swap the root 97 with the last element 49: - [49, 76, 65, 49, 38, 13, 27, 97] - Heap size shrinks to 7.

  3. Restore the first 7 elements into a max-heap: - [76, 49, 65, 49, 38, 13, 27]

  4. Swap the root 76 with the 7th element 27: - [27, 49, 65, 49, 38, 13, 76, 97] - Heap size becomes 6.

  5. Keep repeating “adjust then swap” until the heap size becomes 1.

Final result:

  • [13, 27, 38, 49, 49, 65, 76, 97]

Python implementation

def heap_sort(arr):
    """
    堆排序（升序，基于大顶堆）
    :param arr: 待排序数组（列表）
    :return: 排序后的数组（不修改原数组）
    """
    arr_copy = arr.copy()
    n = len(arr_copy)

    def sift_down(arr, start, end):
        """
        堆调整函数（下沉）：将以start为根的子树调整为大顶堆
        :param start: 子树根节点索引
        :param end: 堆的最后一个元素索引
        """
        root = start
        while True:
            # 左子节点索引
            child = 2 * root + 1
            # 子节点超出堆范围则退出
            if child > end:
                break
            # 选择左右子节点中较大的那个
            if child + 1 <= end and arr[child] < arr[child + 1]:
                child += 1
            # 若根节点 < 子节点，交换并继续下沉
            if arr[root] < arr[child]:
                arr[root], arr[child] = arr[child], arr[root]
                root = child
            else:
                break

    # 1. 构建大顶堆（从最后一个非叶子节点开始调整）
    # 最后一个非叶子节点索引：n//2 - 1
    for i in range(n // 2 - 1, -1, -1):
        sift_down(arr_copy, i, n - 1)

    # 2. 交换堆顶与末尾，调整堆结构
    for end in range(n - 1, 0, -1):
        arr_copy[0], arr_copy[end] = arr_copy[end], arr_copy[0]
        sift_down(arr_copy, 0, end - 1)

    return arr_copy

# 测试用例
if __name__ == "__main__":
    test_arr = [49, 38, 65, 97, 76, 13, 27, 49]
    result = heap_sort(test_arr)
    print("原始数组：", test_arr)
    print("堆排序后：", result)  # [13, 27, 38, 49, 49, 65, 76, 97]

What matters in the code

  1. The sift_down function - This is the heap-adjustment step. - Starting from a root node, it checks the left and right children, picks the larger one, and swaps if the child is larger than the root. - Then it continues sinking the root downward until heap order is restored.

  2. Building the max-heap - Start from the last non-leaf node, which is at index n//2 - 1. - Move backward toward index 0, calling sift_down for each subtree. - This ensures the entire array satisfies the max-heap property.

  3. Sorting phase - Swap the heap top, which is the current maximum, with the last element in the heap. - Reduce the heap boundary by one. - Reapply sift_down so the remaining part becomes a max-heap again. - Repeat until the heap contains only one element.

Characteristics and possible optimizations

Advantages

  • Stable O(n log n) time behavior overall: heap construction is O(n), and repeated heap adjustment gives O(n log n).
  • It is an in-place sort, so space complexity is O(1).
  • Well suited to large datasets.

Disadvantages

  • It is not stable, because moving the root to the end can change the relative order of equal elements.
  • For small datasets, it is often slower than insertion sort or selection sort because heap maintenance adds overhead.
  • It is not cache-friendly, since accesses are not as contiguous as in some other algorithms.

Optimization ideas

  • Use a min-heap if descending order is needed.
  • Combine it with insertion sort for very small heaps, such as subheaps of length under 10.
  • More advanced heap structures like Fibonacci heaps can improve some theoretical operations, though they are rarely used in practical sorting due to implementation complexity.

3. Merge Sort

Core idea

Merge sort is a classic divide-and-conquer algorithm. Its guiding pattern is simple: split first, merge later.

The process has two stages:

  • Divide: recursively split the array into two roughly equal halves until each subarray has length 1.
  • Merge: combine two already sorted subarrays into a larger sorted array.

Its defining step is the merge operation itself, usually implemented with two pointers scanning the two sorted halves. Merge sort is also a standard example of a stable sort.

How it runs

Using [49, 38, 65, 97, 76, 13, 27, 49]:

Split phase

  • Original array
  • [49,38,65,97] + [76,13,27,49]
  • Split again
  • [49,38] + [65,97] + [76,13] + [27,49]
  • Final split
  • [49] + [38] + [65] + [97] + [76] + [13] + [27] + [49]

At this point, each subarray has length 1 and is naturally sorted.

Merge phase

  • Merge [49] and [38] → [38,49]
  • Merge [65] and [97] → [65,97]
  • Merge [76] and [13] → [13,76]
  • Merge [27] and [49] → [27,49]

Then continue upward:

  • Merge [38,49] and [65,97] → [38,49,65,97]
  • Merge [13,76] and [27,49] → [13,27,49,76]

Final merge:

  • [38,49,65,97] and [13,27,49,76]
  • Result: [13, 27, 38, 49, 49, 65, 76, 97]

Python implementation

def merge_sort(arr):
    """
    归并排序（递归实现，升序）
    :param arr: 待排序数组（列表）
    :return: 排序后的数组（不修改原数组）
    """
    # 基线条件：子数组长度≤1时直接返回
    if len(arr) <= 1:
        return arr.copy()

    # 1. 拆分：找到中间索引，拆分为左右子数组
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])

    # 2. 合并：双指针合并两个有序子数组
    def merge(left_arr, right_arr):
        merged = []
        i = j = 0
        # 双指针遍历，取较小值加入结果
        while i < len(left_arr) and j < len(right_arr):
            if left_arr[i] <= right_arr[j]:
                merged.append(left_arr[i])
                i += 1
            else:
                merged.append(right_arr[j])
                j += 1
        # 追加剩余元素（左/右子数组可能有未遍历完的元素）
        merged.extend(left_arr[i:])
        merged.extend(right_arr[j:])
        return merged

    return merge(left, right)

# 测试用例
if __name__ == "__main__":
    test_arr = [49, 38, 65, 97, 76, 13, 27, 49]
    result = merge_sort(test_arr)
    print("原始数组：", test_arr)
    print("归并排序后：", result)  # [13, 27, 38, 49, 49, 65, 76, 97]

What matters in the code

  1. Divide step - If the subarray length is <= 1, return it directly. - Otherwise, compute mid, split into arr[:mid] and arr[mid:], and recursively sort both sides.

  2. Merge step - Use two pointers i and j for the left and right sorted arrays. - Compare left[i] and right[j], append the smaller one, and move the corresponding pointer. - Once one side is exhausted, append all remaining elements from the other side.

Characteristics and possible optimizations

Advantages

  • It is stable: equal elements keep their original relative order during merging.
  • Its time complexity stays at O(n log n) even in the worst case.
  • It works especially well for external sorting, where not all data can fit in memory at once.

Disadvantages

  • It requires extra space of O(n) for merged results.
  • Recursive implementations also incur call stack overhead, though iterative versions can avoid that.

Optimization ideas

  • Use in-place merging to reduce extra memory, though implementation becomes much more complicated.
  • When subarrays are very small, such as length under 15, switch to insertion sort to reduce recursion and merge overhead.
  • Use multiway merging instead of always splitting into just two parts to reduce the number of merge rounds in some scenarios.

4. Radix Sort

Core idea

Radix sort belongs to the family of distribution-based sorting algorithms. Instead of comparing elements directly, it sorts them digit by digit.

The version here uses the LSD strategy—least significant digit first:

  • distribute elements into buckets according to the current digit
  • collect them back in bucket order
  • repeat from the ones place to the tens place, hundreds place, and so on

It only works for data that can be broken down digit by digit, such as integers or strings.

How it runs

Using [49, 38, 65, 97, 76, 13, 27, 49]:

  1. Initial array: - [49, 38, 65, 97, 76, 13, 27, 49]

  2. Sort by the ones digit: - Digits are 9, 8, 5, 7, 6, 3, 7, 9 - Buckets receive:

    • bucket 3: 13
    • bucket 5: 65
    • bucket 6: 76
    • bucket 7: 97, 27
    • bucket 8: 38
    • bucket 9: 49, 49
    • Collecting buckets in order gives:
    • [13, 65, 76, 97, 27, 38, 49, 49]

  3. Sort by the tens digit: - Tens digits are 1, 6, 7, 9, 2, 3, 4, 4 - Buckets receive:

    • bucket 1: 13
    • bucket 2: 27
    • bucket 3: 38
    • bucket 4: 49, 49
    • bucket 6: 65
    • bucket 7: 76
    • bucket 9: 97
    • Collect again:
    • [13, 27, 38, 49, 49, 65, 76, 97]

At that point, the array is fully sorted.

Python implementation

def radix_sort(arr):
    """
    基数排序（LSD策略，仅处理非负整数）
    :param arr: 待排序数组（列表）
    :return: 排序后的数组（不修改原数组）
    """
    if not arr:
        return []
    arr_copy = arr.copy()
    # 找到最大数，确定需要处理的位数
    max_num = max(arr_copy)
    digit = 1  # 当前处理的位数（个位=1，十位=10，百位=100...）

    while max_num // digit > 0:
        # 初始化10个桶（0~9）
        buckets = [[] for _ in range(10)]
        # 1. 分配：按当前位数字放入对应桶
        for num in arr_copy:
            # 获取当前位的数字
            current_digit = (num // digit) % 10
            buckets[current_digit].append(num)
        # 2. 收集：按桶顺序合并元素
        arr_copy = []
        for bucket in buckets:
            arr_copy.extend(bucket)
        # 处理下一位
        digit *= 10
    return arr_copy

# 扩展：处理负数的基数排序
def radix_sort_with_negative(arr):
    if not arr:
        return []
    # 分离正负数，分别排序后合并
    negatives = [-x for x in arr if x < 0]
    positives = [x for x in arr if x >= 0]
    # 对负数的绝对值排序后反转，恢复负数顺序
    sorted_negatives = [-x for x in reversed(radix_sort(negatives))]
    sorted_positives = radix_sort(positives)
    return sorted_negatives + sorted_positives

# 测试用例
if __name__ == "__main__":
    test_arr = [49, 38, 65, 97, 76, 13, 27, 49]
    result1 = radix_sort(test_arr)
    print("非负基数排序后：", result1)  # [13, 27, 38, 49, 49, 65, 76, 97]

    test_arr2 = [49, -38, 65, -97, 76, 13, -27, 49]
    result2 = radix_sort_with_negative(test_arr2)
    print("支持负数排序后：", result2)  # [-97, -38, -27, 13, 49, 49, 65, 76]

What matters in the code

  1. Determine how many digits are needed - Find the maximum value. - Its number of digits tells us how many rounds are required. - For example, 97 has two digits, so we process ones and tens.

  2. Process digit by digit - Start with digit = 1 for the ones place. - Extract the current digit with (num // digit) % 10. - Place each number into bucket 0 through 9. - Collect buckets in order and move to the next digit.

  3. Handling negative numbers - Separate negatives and non-negatives. - Convert negatives to absolute values, sort them, then reverse the result and restore the signs. - Finally concatenate sorted negatives with sorted positives.

Characteristics and possible optimizations

Advantages

  • It is stable, because the distribute-and-collect process preserves the order of equal elements.
  • It can be very efficient for large collections of integers, with time complexity O(d * (n + r)), where d is the number of digits and r is the radix, usually 10.
  • It does not rely on direct comparisons between elements.

Disadvantages

  • Its scope is limited: it only works naturally for types that can be processed by digits or characters.
  • It needs extra storage, giving space complexity O(n + r).
  • As the number of digits grows, efficiency drops because more passes are required.

Optimization ideas

  • Replace bucket lists with counting sort at each digit to reduce bucket-space overhead.
  • Use an MSD strategy—most significant digit first—when sorting strings or lexicographic data.
  • For binary-oriented data, use a radix like 2^8 so each pass handles one byte and the total number of passes is reduced.

Side-by-side comparison

<table> <thead> <tr> <th>Sorting Algorithm</th> <th>Core idea</th> <th>Average / Worst Time Complexity</th> <th>Stability</th> <th>Space Complexity</th> </tr> </thead> <tbody> <tr> <td>Simple Selection Sort</td> <td>pick the minimum and swap</td> <td>O(n²) / O(n²)</td> <td>Unstable</td> <td>O(1)</td> </tr> <tr> <td>Heap Sort</td> <td>max-heap + root swap</td> <td>O(n log n) / O(n log n)</td> <td>Unstable</td> <td>O(1)</td> </tr> <tr> <td>Merge Sort</td> <td>divide and conquer + merge sorted subarrays</td> <td>O(n log n) / O(n log n)</td> <td>Stable</td> <td>O(n)</td> </tr> <tr> <td>Radix Sort</td> <td>digit-based distribute and collect (LSD)</td> <td>O(d * (n + r)) / O(d * (n + r))</td> <td>Stable</td> <td>O(n + r)</td> </tr> </tbody> </table>

Key takeaways

  • Simple selection sort works best on small datasets where stability is not required, and its central action is always “find the minimum, then swap.”
  • Heap sort offers in-place O(n log n) performance and handles large datasets well, but it is not stable.
  • Merge sort is a stable O(n log n) algorithm with consistently strong performance, though it pays for that with extra memory usage.
  • Radix sort avoids comparison-based ordering altogether and is well suited to integers or strings, but digit count and negative-number handling both matter in practice.

Related Posts