归并排序原理与力扣算法实战解析

1. 归并排序与力扣算法题解析

归并排序作为分治算法的经典代表，在力扣（LeetCode）算法题库中有着广泛的应用场景。这个排序算法之所以备受面试官青睐，关键在于它稳定的O(nlogn)时间复杂度以及处理链表排序时的独特优势。在实际刷题过程中，我发现很多涉及逆序对、区间合并的题目，本质上都是归并排序的变种应用。

1.1 归并排序的核心思想

归并排序采用典型的分治策略：将原始数组不断二分，直到子数组长度为1（天然有序），然后通过合并两个有序数组的操作逐级向上归并。这个"分而治之"的过程体现在三个关键步骤：

1. 分解：将当前区间一分为二
2. 解决：递归排序两个子区间
3. 合并：将两个已排序子数组合并为一个有序数组

python复制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)

注意：递归终止条件必须是len(arr) <= 1而不是==1，否则处理空数组时会出错

1.2 合并操作的实现技巧

合并两个有序数组是归并排序的核心操作，也是面试中常考的编码环节。标准的双指针实现如下：

python复制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

这里有几个优化点值得注意：

• 使用extend替代逐个append剩余元素
• 稳定排序的关键在于<=而非<的判断
• 空间复杂度为O(n)，这是归并排序的主要缺点

2. 力扣中的归并排序变种题

2.1 逆序对问题（剑指 Offer 51）

计算数组中的逆序对数量是归并排序的经典应用。在合并过程中，当右子数组元素小于左子数组元素时，左子数组剩余元素都与该右元素构成逆序对：

python复制def reversePairs(nums):
    def merge_sort(l, r):
        if l >= r:
            return 0
            
        mid = (l + r) // 2
        count = merge_sort(l, mid) + merge_sort(mid+1, r)
        
        # 统计逆序对
        j = mid + 1
        for i in range(l, mid+1):
            while j <= r and nums[i] > nums[j]:
                j += 1
            count += j - (mid + 1)
        
        # 合并操作
        nums[l:r+1] = sorted(nums[l:r+1])
        return count
    
    return merge_sort(0, len(nums