Merge Sort

Idea

Merge Sort uses divide-and-conquer: split the array into halves, sort each, then merge them into an ordered array.

归并排序演示

84571362

当前归并区间: [0, 1]

下一步

Algorithm

1. Recursively split into halves until single-element subarrays.
2. Merge pairs of subarrays in order to form sorted sequences.
3. Repeat merging until fully sorted.

Pseudo-code:

function mergeSort(A, left, right):
    if left < right:
        mid = (left + right) // 2
        mergeSort(A, left, mid)
        mergeSort(A, mid+1, right)
        merge(A, left, mid, right)

function merge(A, left, mid, right):
    create tmp
    i = left, j = mid+1, k = 0
    while i <= mid and j <= right:
        if A[i] <= A[j]:
            tmp[k++] = A[i++]
        else:
            tmp[k++] = A[j++]
    copy remaining to tmp
    copy tmp back to A[left..right]

Complexity

• Best/worst/avg: $O(n\log n)$
• Space: $O(n)$
• Stability: stable

Exercises

Exercise 1

Run merge sort on $A = [8, 4, 5, 7, 1, 3, 6, 2]$; show the first merge result.

参考答案

思路：分组后两两归并。

步骤：

1. 初始分组：[8,4],[5,7],[1,3],[6,2]
2. 第一次归并：[4,8],[5,7],[1,3],[2,6]

答案：如上，第一次归并后每组有序。

Exercise 2

What are merge sort’s time and space complexities?

参考答案

思路：复杂度与空间。

步骤：

1. 时间复杂度 $O(n\log n)$
2. 空间复杂度 $O(n)$

答案：时间 $O(n\log n)$，空间 $O(n)$。

PreviousHeap SortHeap sort fundamentals, algorithm flow, complexity, and practice. NextRadix SortRadix sort basics, algorithm flow, complexity, and practice.