归并排序算法详解与实现

算法概述

归并排序（Merge sort）是一种采用“分治”策略的高效排序算法，属于比较类排序算法。其核心思想是将数组递归分割成最小单元（单个元素），然后通过合并操作将有序子数组逐步组合成完整有序数组。

算法特性

• 时间复杂度：最坏情况下 O(n log n)
• 空间复杂度：需要额外 O(n) 空间
• 稳定性：稳定排序算法
• 适用性：适合处理大规模数据集，但对小规模数据效率较低

算法步骤

分割阶段

1. 将数组平均分割为两个子数组
2. 递归地对每个子数组继续分割，直到获得单个元素数组
3. 单个元素数组自然有序

合并阶段

合并两个已排序数组的算法：

1. 初始化三个指针：

   • i：指向数组A的当前元素
   • j：指向数组B的当前元素
   • k：指向合并数组C的当前位置

2. 比较A[i]和B[j]，将较小元素放入C[k]

3. 移动相应指针（i或j）和k指针

4. 重复步骤2-3直到某个数组遍历完毕

5. 将剩余未遍历元素复制到数组C

具体示例

以数组[14, 33, 27, 10, 35, 19, 42, 44]为例：

第一次分割： [14, 33, 27, 10] 和 [35, 19, 42, 44]

继续分割： [14, 33], [27, 10], [35, 19], [42, 44]

最终分割： [14], [33], [27], [10], [35], [19], [42], [44]

合并过程：

• 合并[14]和[33] → [14, 33]
• 合并[27]和[10] → [10, 27]
• 合并[35]和[19] → [19, 35]
• 合并[42]和[44] → [42, 44]

继续合并：

• 合并[14, 33]和[10, 27] → [10, 14, 27, 33]
• 合并[19, 35]和[42, 44] → [19, 35, 42, 44]

最终合并： 合并[10, 14, 27, 33]和[19, 35, 42, 44] → [10, 14, 19, 27, 33, 35, 42, 44]

Java实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

public class MergeSort {
    public static void mergeSort(int[] array) {
        if (array.length < 2) return;
        
        int mid = array.length / 2;
        int[] left = Arrays.copyOfRange(array, 0, mid);
        int[] right = Arrays.copyOfRange(array, mid, array.length);
        
        mergeSort(left);
        mergeSort(right);
        
        merge(array, left, right);
    }
    
    private static void merge(int[] result, int[] left, int[] right) {
        int i = 0, j = 0, k = 0;
        
        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) {
                result[k++] = left[i++];
            } else {
                result[k++] = right[j++];
            }
        }
        
        while (i < left.length) {
            result[k++] = left[i++];
        }
        
        while (j < right.length) {
            result[k++] = right[j++];
        }
    }
}

算法分析

归并排序的主要优势在于其稳定的O(n log n)时间复杂度，无论输入数据的初始状态如何。缺点是需要额外的内存空间，对于内存受限的环境可能不太适合。

该算法特别适合以下场景：

• 需要稳定排序的情况
• 处理大规模数据集
• 链表结构的排序（只需要O(1)额外空间）

归并排序是许多编程语言标准库中排序函数的实现基础，体现了分治策略在算法设计中的强大威力。