归并排序

基本思想

归并排序是稳定的排序算法。归并排序使用的是分治思想，将一个大问题分解为小的子问题来解决。分治算法一般都是用递归来实现的。
要对数组区间[p, r]的数据进行排序，我们先将数据拆分为两部分[p, q]和[q+1, r]，其中q为中间位置。对两部分数据排好序后，我们再将两个子数组合并在一起。当数组的起始位置小于等于终止位置时，说明此时只有一个元素，递归也就结束了。
我们先建立一个临时数组，然后从两个子数组的起始位置开始比较，将较小的元素一个一个放入临时数组，直到其中一个子数组比较完毕，再将剩下的另一个子数组余下的值全部放到临时数组后面。最后我们需要将临时数组中的数据拷贝到原数组对应的位置。

C/C++实现

# include <iostream>
# include <vector>

using namespace std;

class Solution {
public:
    void merge(vector<int> &nums, int left, int mid, int right) {
        vector<int> temp(right - left + 1);
        int i = left, j = mid + 1, k = 0;
        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j])
                temp[k++] = nums[i++];
            else
                temp[k++] = nums[j++];
        }
        while (i <= mid)
            temp[k++] = nums[i++];
        while (j <= right)
            temp[k++] = nums[j++];
        for (int m = 0; m < right - left + 1; m++)
            nums[m + left] = temp[m];
    }

    void merge_sort(vector<int> &nums, int left, int right) {
        if (left >= right)
            return;
        int mid = (left + right) / 2;
        merge_sort(nums, left, mid);
        merge_sort(nums, mid + 1, right);
        merge(nums, left, mid, right);
    }
};

int main() {
    vector<int> a = {5, 2, 3, 4, 7, 5, 1, 6};
    Solution s;
    s.merge_sort(a, 0, a.size() - 1);
    for (int i:a)
        cout << i << " ";
    return 0;
}

Python3实现

class Solution(object):
    def merge(self, nums, left, mid, right):
        temp = []
        i, j = left, mid + 1
        while i <= mid and j <= right:
            if nums[i] <= nums[j]:
                temp.append(nums[i])
                i += 1
            else:
                temp.append(nums[j])
                j += 1
        while i <= mid:
            temp.append(nums[i])
            i += 1
        while j <= right:
            temp.append(nums[j])
            j += 1
        for i in range(len(temp)):
            nums[i + left] = temp[i]

    def merge_sort(self, nums, left, right):
        if left >= right:
            return
        mid = int((left + right) / 2)
        self.merge_sort(nums, left, mid)
        self.merge_sort(nums, mid + 1, right)
        self.merge(nums, left, mid, right)


a = [5, 2, 3, 4, 7, 5, 1, 6]
s = Solution()
s.merge_sort(a, 0, len(a) - 1)
print(a)