归并排序（Merge Sort）采用了分治思想（分而治之）
分治思想即为了解决一个特定的问题，将问题分为很多个小的子问题，之后对这些子问题进行递归，一边递归一边拆分子问题直至无法拆分。拆分完毕后，将这些独立的子问题解决，将每个子问题解决的答案加在一起就是一整个问题的答案。
首先是归并排序在《算法导论》中的一个简单表现例子：
有两幅扑克牌背面朝下放在桌子上，最小的牌在牌堆的最上面。目的是将两幅牌面朝下（最小牌在下）合成一副牌盖在桌子上。我们要做的就是比较两副牌牌堆顶谁点数小，就把谁的牌堆顶牌拿下背朝上盖在桌子上。依次类推，直至两个牌堆中的一个为空，之后要做的就是把剩下的牌堆不需要进行任何操作，背朝上盖在目标牌堆上就好了。
上面的过程就是分治思想中的治
程序中的数组同理，假设我们有串数据，内容是5，2，4，7，1，3，2，6，我把数组均分成两部分，但两部分数组仍然是无序的，为了使两个数组有序（这样才能做到上面的治，即数组第一个元素作比较），我们需要把每个子数组分到直至只有一个元素。最后我们能分出来八个独立元素，两两之间作比较，就能合并出四个有两个元素的有序数组，不停合并（合并过程中穿插着子数组之间的归并排序，依次比较两个数组的最小值谁更小，将其放入到要合并的数组当中去）到只有一个八元素数组。
C++代码
1 void mergeSort(vector<int>& nums) { 2 int left = 0, right = nums.size() - 1; 3 vector<int> temp(nums.size()); //临时数组，用于存放递归过程中的数据 4 mergeSortStep(nums, left, right, temp); 5 } 6 void mergeSortStep(vector<int>& nums, int left, int right, vector<int>& temp) { 7 //递归终止条件，即分到只剩下一个元素 8 if (left < right) { 9 int middle = (left + right) / 2; //均分 10 mergeSortStep(nums, left, middle, temp); //对分出来的左半部分继续均分 11 mergeSortStep(nums, middle + 1, right, temp); //对分出来的右半部分继续均分 12 merge(nums, left, middle, right, temp); //归并操作 13 } 14 } 15 void merge(vector<int>& nums, int left, int middle, int right, vector<int>& temp) { 16 int leftIndex = left, rightIndex = middle + 1; 17 int index = left; //临时数组的索引值 18 //比较操作，小的元素依次放到临时数组temp中，直至左右两部分有一部分空了 19 while (leftIndex != middle + 1 && rightIndex != right + 1) { 20 if (nums[leftIndex] <= nums[rightIndex]) { 21 temp[index] = nums[leftIndex]; 22 index++; 23 leftIndex++; 24 } 25 else { 26 temp[index] = nums[rightIndex]; 27 index++; 28 rightIndex++; 29 } 30 } 31 //找到没空的那部分，依次放入到temp临时数组中 32 if (leftIndex == middle + 1) { 33 for (int i = rightIndex; i <= right; i++, index++) { 34 temp[index] = nums[i]; 35 } 36 } 37 else if(rightIndex == right + 1){ 38 for (int i = leftIndex; i <= middle; i++, index++) { 39 temp[index] = nums[i]; 40 } 41 } 42 //一次归并操作完成，把之前操作过的部分赋值到原始数组中 43 for (int i = left, j = left; i <= right; i++, j++) { 44 nums[i] = temp[j]; 45 } 46 }
因为要提前建立一个临时数组，所以空间复杂度是O(N)，而时间复杂度则是由于对半分而不是遍历的关系则是O(NlogN)
原文：https://www.cnblogs.com/soulkeyboy969/p/15270150.html