原理
现在有两个数组a, b，都是有序的，要你将他们合并成一个数组，你会怎么做呢，当然不会直接合并再排序了，而是如下操作
1. 设两标志指针分别指向a,b的首元素。
2. 比较当前a,b当前首位元素，选择较小的加入临时数组t，相应的标志指针后移。
3. 重复2过程，知道a.b任一方已全部加入t，然后到步骤4
4. 将未完全加入的数组剩余元素全部加入。
这样合并两个数组的时间复杂度是O(len(a) + len(b))。
那么联想到归并排序，我们已经能大致猜出来他的排序的流程啦。如下图所示。
没错，归并排序就是不断的将数组二分，直到元素数为1，然后再合并(如上面说到的合并数组)，形成有序的序列，是一个快速且稳定的排序算法
代码
原理很好理解，不做赘述，明白原理后，写出递归的归并排序是很容易的，下面会贴出递归的代码。
今天主要说下非递归的思路。
递归式的思想是先二分再合并的一个流程。而我们非递归时可以直接对它们进行合并，而不必二分(事实上每个元素都在各自下标处，完全可以当作已经二分好了)，当然，这里的边界什么的需要自己用循环来规定了。
而且非递归相比递归还有一个特殊的地方，比如下面这个序列
8 3 4 5 7 2 1 3
递归的情况下，不会考虑它们的数值，而是直接进行二分，我们最终会进行4+2+1=7次合并操作。
但我们在非递归下就可以趁机对此改进。比如3 4 5 7，我们完全没有必要去将它们二分，因为它们已经是有序的了，只需要将其与相邻序列串合并就好。
那么我们会将其分为这些序列
8 ｜ 3 4 5 7 ｜ 2 ｜ 1 3
然后将8 与 3 4 5 7 合并为 3 4 5 7 8
同理，2与1 3为 1 2 3
再合并即为 1 2 3 3 4 5 7 8
我们只用了3次合并操作，对比递归已经好了很多。
不说了，上代码
代码
非递归
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<queue>
using namespace std;
#define LL long long
const int N = 21;
int d[N];
int t[N];
void func(const pair<int, int> &a, const pair<int, int> &b)
{
int i=0;
for(int sa = a.first, sb = b.first; sa<=a.second || sb<=b.second;)
{
if(sa <= a.second && sb <= b.second)
{
if(d[sa] <= d[sb])
t[i++] = d[sa++];
else
t[i++] = d[sb++];
}
else if(sa <= a.second)
t[i++] = d[sa++];
else
t[i++] = d[sb++];
}
for(int j=0; j<i; j++)
d[j+a.first] = t[j];
}
void merge_sort(int st, int end)
{
while(1)
{
int l = st;
vector<pair<int, int>> v;
for(int i=st+1; i<=end; i++)
{
if(d[i] < d[i-1])
{
v.push_back(pair<int, int>(l, i-1));
l = i;
}
}
if(l == st)
break;
v.push_back(pair<int, int>(l, end));
for(int i=1; i<v.size(); i+=2)
func(v[i-1],v[i]);
}
}
int main()
{
int n;
cin>>n;
for(int i=0; i<n; i++)
cin>>d[i];
merge_sort(0, n-1);
for(int i=0; i<n; i++)
cout<<d[i]<<" ";
cout<<endl;
return 0;
}递归
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<queue>
using namespace std;
#define LL long long
const int N = 21;
int d[N];
int t[N];
void func(const pair<int, int> &a, const pair<int, int> &b)
{
int i=0;
for(int sa = a.first, sb = b.first; sa<=a.second || sb<=b.second;)
{
if(sa <= a.second && sb <= b.second)
{
if(d[sa] <= d[sb])
t[i++] = d[sa++];
else
t[i++] = d[sb++];
}
else if(sa <= a.second)
t[i++] = d[sa++];
else
t[i++] = d[sb++];
}
for(int j=0; j<i; j++)
d[j+a.first] = t[j];
}
void merge_sort(int st, int ed)
{
if(st >= ed)
return;
int mid = st+(ed-st)/2;
tmerge_sort(st, mid);
tmerge_sort(mid+1, ed);
func(pair<int, int>(st, mid), pair<int, int> (mid+1, ed));
}
int main()
{
int n;
cin>>n;
for(int i=0; i<n; i++)
cin>>d[i];
merge_sort(0, n-1);
for(int i=0; i<n; i++)
cout<<d[i]<<" ";
cout<<endl;
return 0;
}