归并排序：原理、代码实现与复杂度分析

归并排序详解

一、核心思路

归并排序（Merge Sort）是典型的分治算法。我们可以这样理解它的逻辑：

• 快速排序：整个数组有序 = 基准元素有序 + 左侧子数组有序 + 右侧子数组有序。
• 归并排序：整个数组有序 = 左半部分有序 + 右半部分有序 + 两个有序子数组合并。

简单来说，就是把大问题拆解成小问题，解决小问题后，再把结果合并起来。

1. 边界处理

在递归过程中，我们需要先定义好终止条件，避免无效计算：

• array == null：空数组无需排序。
• left == right：只有一个元素时，天然有序，直接返回。
• left > right：区间非法，直接返回。

2. 合并操作

当递归回到上一层时，左右两个子数组都已经有序了。此时只需要执行一次标准的'双指针合并'操作，将两个有序数组合并为一个更大的有序数组。

3. 算法本质

从底层的最小单元（单个元素）开始，自底向上地不断合并，直到最终形成一个完整的有序数组。

二、代码实现

下面是基于 Java 的完整实现。注意看 merge 函数中的双指针逻辑，这是归并排序的关键。

public static void mergeSort(int[] array) {
    if (array == null || array.length < 2) return;
    mergeSortFunc(array, 0, array.length - 1);
}

private static void mergeSortFunc(int[] array, int left, int right) {
    // 递归终止条件：区间内只有一个元素或非法区间
     (left >= right) ;
    
       left + ((right - left) >> ); 
    
    
    mergeSortFunc(array, left, mid);
    
    mergeSortFunc(array, mid + , right);
    
    merge(array, left, right, mid);
}

    {
       left;      
       mid + ;   
    [] tmpArr =  [right - left + ]; 
       ;

    
     (s1 <= mid && s2 <= right) {
         (array[s1] <= array[s2]) {
            tmpArr[k++] = array[s1++];
        }  {
            tmpArr[k++] = array[s2++];
        }
    }

    
     (s1 <= mid) {
        tmpArr[k++] = array[s1++];
    }
     (s2 <= right) {
        tmpArr[k++] = array[s2++];
    }

    
     (   ; i < tmpArr.length; i++) {
        array[i + left] = tmpArr[i];
    }
}