排序算法之：归并排序的优化——原地归并排序（In-Place Merge Sort）

题目描述
给定一个整数数组，要求使用原地归并排序算法对其进行升序排序。与传统的归并排序不同，原地归并排序不允许使用额外的O(n)空间来合并两个有序子数组，而是通过巧妙的元素交换和旋转操作，在O(1)的额外空间复杂度内完成合并。目标是理解并实现这一优化版本，分析其时间复杂度和操作细节。

解题过程循序渐进讲解

1. 传统归并排序的空间瓶颈
传统归并排序采用分治策略：

• 分解：将数组递归分成两半，直到子数组长度为1。
• 合并：将两个有序子数组合并成一个有序数组，需要临时数组存储合并结果。
  合并操作的空间复杂度为O(n)，成为排序大规模数据时的瓶颈。

2. 原地归并的核心思想
原地归并的目标是在O(1)额外空间下合并两个相邻有序子数组arr[left:mid]和arr[mid:right]。核心思路包括：

• 指针交换法：用两个指针分别遍历左右子数组，通过交换元素使较小值前置。
• 块旋转法：当需要保留较长有序段时，通过旋转操作（类似数组循环移位）调整顺序。

3. 关键操作：循环交换算法（Cycle Swap）
假设左子数组为L，右子数组为R，合并时若发现L[i] > R[j]，需将R[j]插入到L[i]前。步骤：

1. 在L中找到第一个大于R[j]的元素位置i。
2. 在R中找到最后一个小于等于L[i]的元素位置j（确保稳定性）。
3. 将L[i...mid]与R[0...j]进行块旋转：
   • 旋转后，R[0...j]位于L[i...mid]前，形成有序序列。
   • 旋转操作通过三次反转实现（反转L[i...mid]，反转R[0...j]，反转整体）。

示例：
数组[1, 3, 5, 2, 4, 6]，左子数组[1,3,5]，右子数组[2,4,6]。

• 比较发现5 > 2，旋转[5]和[2]：先反转[5]得[5]，反转[2]得[2]，反转[5,2]得[2,5]，数组变为[1,3,2,5,4,6]。
• 继续处理剩余部分。

4. 时间复杂度分析

• 每次合并操作的时间复杂度为O(m×n)，其中m和n为子数组长度（因块旋转需扫描元素）。
• 总时间复杂度为O(n² log n)，比传统归并排序的O(n log n)差，但空间复杂度优化为O(1)。
• 实际应用中，此方法适用于对空间敏感但时间要求不严格的场景。

5. 实现步骤

def reverse(arr, start, end):
    """反转数组区间[start, end]"""
    while start < end:
        arr[start], arr[end] = arr[end], arr[start]
        start += 1
        end -= 1

def rotate(arr, start, mid, end):
    """旋转左子数组[start:mid]和右子数组[mid:end]"""
    reverse(arr, start, mid - 1)
    reverse(arr, mid, end)
    reverse(arr, start, end)

def in_place_merge(arr, left, mid, right):
    """合并arr[left:mid]和arr[mid:right]"""
    i, j = left, mid
    while i < j and j <= right:
        if arr[i] <= arr[j]:
            i += 1
        else:
            # 找到右子数组中小于arr[i]的连续段
            k = j
            while k <= right and arr[k] < arr[i]:
                k += 1
            # 旋转左子数组从i到mid-1和右子数组从j到k-1
            rotate(arr, i, j, k - 1)
            i += k - j  # 更新i指针
            j = k

def in_place_merge_sort(arr, left, right):
    """递归进行原地归并排序"""
    if left < right:
        mid = (left + right) // 2
        in_place_merge_sort(arr, left, mid)
        in_place_merge_sort(arr, mid + 1, right)
        in_place_merge(arr, left, mid + 1, right)

6. 优化与权衡

• 原地归并排序牺牲时间效率换取空间效率，适用于嵌入式系统或内存受限环境。
• 若对稳定性有要求，需在旋转时保持相等元素的原始顺序。
• 可结合插入排序优化小规模子数组（如长度<10时使用插入排序），减少递归开销。

通过以上步骤，你可以在仅使用O(1)额外空间的情况下完成数组排序，深入理解时间与空间的权衡在算法设计中的重要性。