https://leetcode-cn.com/problems/sort-an-array/

基于分治的思想，是一种稳定的排序算法，主要过程是将数组从中间分成两部分，然后将两个子数组继续分解，直到所有部分的元素个数都为1。然后从最底层开始将两个有序的子数组有序合并，通过递归，层层合并，最后得到一个有序的大数组。

  • 时间复杂度 O(n*logn)
    • n : 合并的时间复杂度
    • logn：递归深度，合并次数
  • 空间复杂度 O(n)
    1. class Solution {
    2. public:
    3.   vector<int> sortArray(vector<int>& nums) {
    4.       mergeSort(nums, 0, nums.size() - 1);
    5.       return nums;
    6.   }
    7.   // 将数组从中间分为两部分，然后将两个子数组继续分解，直到所有部分元素为1，使用递归从底开始层层合并。
    8.   void mergeSort(vector<int> &nums, int l, int r) {
    9.       if (l >= r) return;
    10.       int mid = l + (r - l) / 2;
    11.       mergeSort(nums, l, mid);
    12.       mergeSort(nums, mid + 1, r);
    13.       merge(nums, l, mid, r);
    14.   }
    15.   // 有序合并两个有序的子数列
    16.   void merge(vector<int> &nums, int l, int mid, int r) {
    17.       vector<int> tmp(r - l + 1);
    18.       int i = l, j = mid + 1, k = 0;
    19.       while (i <= mid && j <= r) {
    20.           if (nums[i] <= nums[j]) tmp[k++] = nums[i++];
    21.           else tmp[k++] = nums[j++];
    22.       }
    23.       while (i <= mid) tmp[k++] = nums[i++];
    24.       while (j <= r) tmp[k++] = nums[j++];
    25.       for (int n : tmp) {
    26.           nums[l++] = n;
    27.       }
    28.   }
    29. };

    为什么内置算法用快排不用归并排序

    虽然归并排序的时间复杂度比较稳定，但是归并排序不是原地排序算法，需要额外的空间，空间复杂度是O(n)。
    虽然最坏情况下快排的时间复杂度是O(n2)，但是它们的平均时间复杂度都是O(n*logn)，而且还可以通过随机选择基准值来避免这种最坏的情况。