力扣912排序题终极解法：递归分割 + 双指针合并详解

题目解读

给定一个整数数组，要求将其按升序排列并返回。题目通常隐含对算法时间复杂度的要求，理想情况下需实现 O(n log n) 的时间复杂度。本题看似简单，但需要选择合适的排序算法（如归并排序、快速排序等），且需避免直接调用语言内置的排序函数。提供的代码通过归并排序的分治思想解决了这一问题，通过递归分割数组并合并有序子数组完成排序。

解题思路与过程

采用经典的归并排序算法实现排序，主要分为以下步骤：

1.递归分割数组‌：将数组不断二分，直到子数组长度为1（即递归终止条件 l == r）。

2.合并有序子数组‌：将两个已排序的子数组合并为一个有序数组。合并时使用双指针遍历左右子数组的元素，依次选择较小的值存入临时数组 tmp，最终将 tmp 的结果覆盖原数组的对应区间。

3.临时数组的利用‌：在合并过程中，通过全局临时数组 tmp[50000] 保存合并结果，避免多次动态内存分配。

代码：

class Solution {  
public:  
    int tmp[50000];  // 全局临时数组，用于合并过程中的中间存储  
    void mysort(vector<int>& nums, int l, int r) {  
        if (l == r) {  // 递归终止条件：子数组长度为1  
            return;  
        }  
        int mid = (l + r) / 2;  
          
        // 递归分割左半部分  
        mysort(nums, l, mid);  
        // 递归分割右半部分  
        mysort(nums, mid + 1, r);  
          
        int index = l;    // 合并结果的起始位置  
        int lnow = l;     // 左子数组的指针  
        int rnow = mid + 1;  // 右子数组的指针  
          
        // 合并左右子数组  
        while (lnow <= mid || rnow <= r) {  
            if (rnow > r) {  // 右子数组已遍历完，直接填充左子数组剩余元素  
                tmp[index] = nums[lnow];  
                lnow++;  
                index++;  
            } else if (lnow > mid) {  // 左子数组已遍历完，填充右子数组剩余元素  
                tmp[index] = nums[rnow];  
                rnow++;  
                index++;  
            } else {  
                // 选择左右子数组中较小者放入临时数组  
                tmp[index] = min(nums[lnow], nums[rnow]);  
                if (nums[lnow] < nums[rnow]) {  
                    lnow++;  
                } else {  
                    rnow++;  
                }  
                index++;  
            }  
        }  
        // 将临时数组结果覆盖到原数组  
        for (int i = l; i <= r; i++) {  
            nums[i] = tmp[i];  
        }  
    }  
      
    vector<int> sortArray(vector<int>& nums) {  
        mysort(nums, 0, nums.size() - 1);  
        return nums;  
    }  
};