递归/分治：归并排序

前言

分治算法:

将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出 子问题的解后进行合并，就可得到原问题的解。

步骤如下:

1. 分解，将要解决的问题划分成若 干规模较小的同类问题;
2. 求解，当子问题划分得足够小时 ，用较简单的方法解决;
3. 合并，按原问题的要求，将子问题 的解逐层合并构成原问题的解。

归并排序

在描述归并排序之前，我们先来看看如何合并两个有序数组，大概过程类似与之前描述过的​​两个有序链表的合并​​

实现过程如下:

void merge_two_arr(std::vector<int> &arr1, 
        std::vector<int> &arr2, 
        std::vector<int> &result) {
  int i = 0;
  int j = 0;
  /*在下标不断累加的过程中优先插入较小的一个元素，且对应的下标累加*/
  while(i < arr1.size() && j < arr2.size()) {
      if (arr1[i] <= arr2[j]) {
        result.push_back(arr1[i]);
        i++;
      } else {
        result.push_back(arr2[j]);
        j++;
      }
  }

  if (i == arr1.size()) { //将剩余的未合并的元素合入
    for (;j < arr2.size(); ++j) {
      result.push_back(arr2[j]);
    }
  } else {
    for (;i < arr1.size(); ++i) {
      result.push_back(arr1[i]);
    }
  }
}      

依据分治算法的步骤，我们回到归并排序的过程上

以上过程即实现了分治算法的第三步：合并；

那么分治算法的第一步：分解，第二步：求解该如何做呢？

显然，我们的一个无序数组同样可以不断得二分，最终拆解为对底层的两两合并，对于每一个分解后的集合，我们同样使用合并有序数组（因为只有两个元素了，要做的就是对两个元素的合并）的过程。

实现如下:

void merge_sort(std::vector<int> &arr) {
  if (arr.size() < 2) {
    return ;
  }

  int mid = arr.size() / 2;
  std::vector<int> arr1;
  std::vector<int> arr2;
  for (int i = 0; i < mid; ++i) {
    arr1.push_back(arr[i]);
  }
  for (int i = mid; i< arr.size(); ++i){
    arr2.push_back(arr[i]);
  }

  merge_sort(arr1);
  merge_sort(arr2);

  arr.clear();
  /*以上递归返回的arr1和arr2为有序数组，最终合并两个有序数组即可*/
  merge_two_arr(arr1,arr2,arr); 
}      

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stdlib.h>

using namespace std;
/*合并两个有序数组*/
void merge_two_arr(std::vector<int> &arr1, std::vector<int> &arr2, std::vector<int> &result) {
  int i = 0;
  int j = 0;
  while(i < arr1.size() && j < arr2.size()) {
      if (arr1[i] <= arr2[j]) {
        result.push_back(arr1[i]);
        i++;
      } else {
        result.push_back(arr2[j]);
        j++;
      }
  }

  if (i == arr1.size()) {
    for (;j < arr2.size(); ++j) {
      result.push_back(arr2[j]);
    }
  } else {
    for (;i < arr1.size(); ++i) {
      result.push_back(arr1[i]);
    }
  }
}
/*归并排序*/
void merge_sort(std::vector<int> &arr) {
  if (arr.size() < 2) {
    return ;
  }

  int mid = arr.size() / 2;
  std::vector<int> arr1;
  std::vector<int> arr2;
  for (int i = 0; i < mid; ++i) {
    arr1.push_back(arr[i]);
  }
  for (int i = mid; i< arr.size(); ++i){
    arr2.push_back(arr[i]);
  }

  merge_sort(arr1);
  merge_sort(arr2);

  arr.clear();
  merge_two_arr(arr1,arr2,arr);
}

int main(int argc, char const *argv[])
{
  std::vector<int> arr;

  int n; 
  cin >> n;
  int tmp;
  for (int i = 0; i < n; ++i) {
    cin >> tmp;
    arr.push_back(tmp);
  } 

  merge_sort(arr);
  for (int i = 0;i < arr.size(); ++i) {
    cout << arr[i] << " ";
  }
  cout << endl;
  return 0;
}      

#输入
5
-7 3 -4 -1 2
#输出
-7 -4 -1 2 3