实现归并排序

题目描述：给定一个整数数组，使用归并排序算法将其按升序排列。归并排序是一种典型的分治算法，通过递归地将数组分成两半分别排序，然后将两个有序子数组合并成一个有序数组。

解题过程：

1. 理解分治思想

   • 归并排序的核心是"分而治之"：将大问题分解成小问题，解决小问题后合并结果
   • 具体步骤：分解→解决→合并

2. 分解阶段

   • 找到数组的中间位置：mid = (left + right) // 2
   • 将数组分成左右两个子数组：
     • 左子数组：从left到mid
     • 右子数组：从mid+1到right
   • 递归地对左右子数组进行归并排序

3. 合并阶段（关键步骤）

   • 创建临时数组存放合并结果
   • 使用双指针法比较两个子数组的元素
   • 将较小的元素依次放入临时数组
   • 将剩余元素复制到临时数组
   • 将临时数组复制回原数组

4. 具体实现细节

   def merge_sort(arr, left, right):
       if left >= right:  # 基线条件：子数组长度为0或1
           return
   
       mid = (left + right) // 2
       merge_sort(arr, left, mid)      # 排序左半部分
       merge_sort(arr, mid + 1, right) # 排序右半部分
       merge(arr, left, mid, right)    # 合并两个有序子数组
   
   def merge(arr, left, mid, right):
       temp = []        # 临时数组
       i, j = left, mid + 1  # 双指针
   
       # 比较并合并
       while i <= mid and j <= right:
           if arr[i] <= arr[j]:
               temp.append(arr[i])
               i += 1
           else:
               temp.append(arr[j])
               j += 1
   
       # 复制剩余元素
       while i <= mid:
           temp.append(arr[i])
           i += 1
       while j <= right:
           temp.append(arr[j])
           j += 1
   
       # 将临时数组复制回原数组
       for k in range(len(temp)):
           arr[left + k] = temp[k]
   

5. 算法特性分析

   • 时间复杂度：O(nlogn)
   • 空间复杂度：O(n)（需要临时数组）
   • 稳定性：稳定排序（相等元素相对位置不变）
   • 适用场景：适合链表排序、外部排序