Mastering Standard Sorting Algorithms: Bubble, Insertion & Merge Sort | 掌握标准排序算法：冒泡、插入与归并排序

📚 Mastering Standard Sorting Algorithms: Bubble, Insertion & Merge Sort | 掌握标准排序算法：冒泡、插入与归并排序

Sorting is a fundamental operation in computer science that organises data into a meaningful order. For A-Level Edexcel programming, understanding standard sorting algorithms such as Bubble Sort, Insertion Sort and Merge Sort is essential—not only to appreciate algorithm design but also to compare their efficiency. This guide brings together the core ideas, pseudocode, Python implementations and complexity analysis for these three classic algorithms.

排序是计算机科学中一项将数据组织成有意义顺序的基本操作。对于 A-Level Edexcel 编程而言，理解冒泡排序、插入排序和归并排序等标准排序算法至关重要——这不仅能帮助理解算法设计，还能比较它们的效率。本指南汇集了这三种经典算法的核心思想、伪代码、Python 实现以及复杂度分析。

1. Introduction to Sorting Algorithms | 排序算法简介

Sorting algorithms rearrange a list of elements into ascending or descending order. In Edexcel A-Level, you are expected to trace, implement and evaluate the performance of at least three sorts. Efficiency is measured by time complexity (Big O notation) and space complexity. An algorithm that performs well on small data sets may become impractical for larger ones, so choosing the right algorithm matters.

排序算法将元素列表重新排列为升序或降序。在 Edexcel A-Level 中，你需要跟踪、实现并评估至少三种排序算法的性能。效率通过时间复杂度（大 O 表示法）和空间复杂度来衡量。在小数据集上表现良好的算法在大数据集上可能变得不切实际，因此选择合适的算法非常重要。

2. Bubble Sort: How It Works | 冒泡排序：工作原理

Bubble Sort repeatedly steps through the list, compares adjacent items and swaps them if they are in the wrong order. Each pass moves the next largest unsorted element to its correct position, like a bubble rising to the surface. This process continues until no swaps are needed—meaning the list is fully sorted.

冒泡排序反复遍历列表，比较相邻元素，如果顺序错误就交换它们。每一趟遍历都将下一个最大的未排序元素移动到正确的位置，就像气泡浮到水面。这个过程一直持续到不再需要交换为止——此时列表已完全有序。

3. Bubble Sort Pseudocode and Python Implementation | 冒泡排序伪代码与 Python 实现

The typical pseudocode for Bubble Sort uses a flag to detect whether any swap occurred during a pass. If a pass completes without a swap, the list is sorted early.

冒泡排序的典型伪代码使用一个标志来检测在一趟遍历中是否发生了交换。如果某一趟完成时没有发生交换，列表已提前有序。

Pseudocode:

PROCEDURE bubbleSort(list)
  n = LENGTH(list)
  REPEAT
    swapped = FALSE
    FOR i = 0 TO n-2
      IF list[i] > list[i+1] THEN
        SWAP list[i], list[i+1]
        swapped = TRUE
      ENDIF
    ENDFOR
    n = n - 1
  UNTIL NOT swapped
ENDPROCEDURE

Python code:

def bubble_sort(arr):
    n = len(arr)
    swapped = True
    while swapped and n > 1:
        swapped = False
        for i in range(n - 1):
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
                swapped = True
        n -= 1
    return arr

Note how the inner loop’s range shrinks because the largest elements are already placed at the end after each pass.

注意内层循环的范围在缩小，因为最大的元素在每趟遍历后已经被放到末尾。

4. Insertion Sort: Core Idea | 插入排序：核心思想

Insertion Sort builds the final sorted list one element at a time. It picks the next unsorted element and inserts it into its correct position within the already sorted portion of the list. This is similar to how you might sort playing cards in your hand.

插入排序一次一个元素地构建最终有序列表。它取出下一个未排序的元素，并将其插入到已排序部分的正确位置。这类似于你整理手中扑克牌的方法。

5. Insertion Sort Pseudocode and Python Example | 插入排序伪代码与 Python 示例

The algorithm starts with the second element and compares it backwards through the sorted sublist, shifting larger elements to the right until the correct spot is found.

该算法从第二个元素开始，在已排序子列表中向后比较，将较大的元素向右移动，直到找到正确的位置。

Pseudocode:

PROCEDURE insertionSort(list)
  FOR j = 1 TO LENGTH(list)-1
    key = list[j]
    i = j - 1
    WHILE i >= 0 AND list[i] > key
      list[i+1] = list[i]
      i = i - 1
    ENDWHILE
    list[i+1] = key
  ENDFOR
ENDPROCEDURE

Python code:

def insertion_sort(arr):
    for j in range(1, len(arr)):
        key = arr[j]
        i = j - 1
        while i >= 0 and arr[i] > key:
            arr[i + 1] = arr[i]
            i -= 1
        arr[i + 1] = key
    return arr

This algorithm is adaptive: it runs quickly on nearly sorted data because the inner loop does very little shifting.

该算法是自适应的：在几乎有序的数据上运行得很快，因为内层循环只需很少的移位操作。

6. Merge Sort: Divide and Conquer | 归并排序：分而治之

Merge Sort is a recursive algorithm that splits the list into halves, recursively sorts each half and then merges the two sorted halves back together. The splitting continues until each sublist contains a single element, which is trivially sorted.

归并排序是一种递归算法，将列表分成两半，递归地对每一半进行排序，然后将两个已有序的半部分合并在一起。拆分一直持续到每个子列表只包含一个元素（自然有序）。

7. Merge Sort Pseudocode (Recursive) | 归并排序伪代码（递归）

The key routines are mergeSort (recursive splitting) and merge (combining two sorted lists). The pseudocode below captures the logical structure.

核心例程是 mergeSort（递归拆分）和 merge（合并两个已排序列表）。下面的伪代码体现了逻辑结构。

FUNCTION mergeSort(list)
  IF LENGTH(list) <= 1 THEN
    RETURN list
  ENDIF
  mid = LENGTH(list) DIV 2
  left = mergeSort(list[0:mid])
  right = mergeSort(list[mid:])
  RETURN merge(left, right)
ENDFUNCTION

FUNCTION merge(left, right)
  result = []
  WHILE left NOT EMPTY AND right NOT EMPTY
    IF left[0] <= right[0] THEN
      APPEND left[0] TO result
      REMOVE first element from left
    ELSE
      APPEND right[0] TO result
      REMOVE first element from right
    ENDIF
  ENDWHILE
  APPEND remaining elements of left and right to result
  RETURN result
ENDFUNCTION

8. Merge Sort Python Implementation | 归并排序 Python 实现

A clean implementation uses slicing and list comprehensions. Although slicing creates new lists (affecting space complexity), it mirrors the pseudocode closely for learning purposes.

清晰的实现使用切片和列表推导。尽管切片会创建新列表（影响空间复杂度），但为了学习目的，它与伪代码非常吻合。

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

Note that the original list is not modified in-place; a new sorted list is returned.

注意原始列表不会被原地修改；会返回一个新的已排序列表。

9. Comparing Time Complexities | 时间复杂度比较

Time complexity describes how the runtime grows with input size n. Bubble Sort and Insertion Sort both have worst‑case and average‑case time complexity O(n²). Merge Sort consistently runs in O(n log n). However, Insertion Sort can achieve O(n) on nearly sorted data, while Bubble Sort can be optimised to stop early (still O(n²) worst case).

时间复杂度描述了运行时间如何随输入规模 n 增长。冒泡排序和插入排序的最坏情况和平均时间复杂度都是 O(n²)。归并排序始终保持 O(n log n)。然而，插入排序在近乎有序的数据上可以达到 O(n)，而冒泡排序可以优化以提前停止（最坏情况仍为 O(n²)）。

Algorithm	Best	Average	Worst
Bubble Sort	O(n)	O(n²)	O(n²)
Insertion Sort	O(n)	O(n²)	O(n²)
Merge Sort	O(n log n)	O(n log n)	O(n log n)

10. Space Complexity Considerations | 空间复杂度考量

Bubble Sort and Insertion Sort are in-place algorithms: they require only a constant amount of additional memory, O(1) auxiliary space. Merge Sort, however, needs extra memory proportional to the list size for the merge process, giving it O(n) space complexity. In environments where memory is limited, in-place sorts may be preferred.

冒泡排序和插入排序是原地算法：它们只需要常量额外内存，辅助空间为 O(1)。而归并排序在合并过程中需要与列表大小成比例的额外内存，空间复杂度为 O(n)。在内存受限的环境中，原地排序可能更受青睐。

11. When to Use Each Algorithm | 何时使用每种算法

Insertion Sort is excellent for small lists or nearly sorted data, and it is stable (preserves the relative order of equal elements). Bubble Sort is simple but rarely used in practice due to its inefficiency. Merge Sort is preferred when stable, O(n log n) worst‑case performance is required, and extra memory is acceptable. For A‑Level exams, focus on comparing these behaviours.

插入排序非常适用于小列表或近乎有序的数据，并且它是稳定的（保持相等元素的相对顺序）。冒泡排序很简单，但由于效率低在实际中很少使用。当需要稳定的、O(n log n) 最坏情况性能且可接受额外内存时，优先选择归并排序。在 A-Level 考试中，要重点比较这些行为。

12. Exam Tips for Edexcel | 爱德思考试技巧

When tracing a sorting algorithm, carefully show the state of the list after each pass or iteration. Edexcel often asks you to complete a trace table. Be ready to identify the number of comparisons and swaps for a given input. Practice writing pseudocode for each sort and ensure you understand the differences in performance characteristics.

在跟踪排序算法时，仔细展示每次遍历或迭代后列表的状态。爱德思考试经常要求你完成跟踪表。准备好识别给定输入的比较次数和交换次数。练习为每种排序编写伪代码，并确保你理解性能特征之间的差异。

Published by TutorHao | Programming Revision Series | aleveler.com

更多咨询请联系16621398022（同微信）

Mastering Standard Sorting Algorithms: Bubble, Insertion & Merge Sort | 掌握标准排序算法：冒泡、插入与归并排序