![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#include <iostream>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#include <cstdio>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
const int N = 100004;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
typedef struct
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
![](http://www.cppblog.com/Images/dot.gif)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int key[N];
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int length;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockEnd.gif)
}SqList;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void Merge(SqList &L, int low, int mid, int high)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
![](http://www.cppblog.com/Images/dot.gif)
{//int p,int q,int r
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int n1, n2;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int i, j, k;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
//=========以下开辟二个辅助数组=========
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
n1 = mid - low + 1;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
n2 = high - mid;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int *Left = new int[n1 + 1], *Right= new int[n2 + 1];
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for(i = 0; i < n1; i++)
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
Left[i] = L.key[low + i];
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for(i = 0;i < n2; i++)
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
Right[i] = L.key[mid + i + 1];
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for(i = j = 0, k = low; k <= high; k++)
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if(i == n1)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
![](http://www.cppblog.com/Images/dot.gif)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
while(k <= high)
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
L.key[k++] = Right[j++];
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
break;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockEnd.gif)
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
else if(j == n2)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
![](http://www.cppblog.com/Images/dot.gif)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
while(k <= high)
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
L.key[k++] = Left[i++];
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
break;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockEnd.gif)
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
else if(Left[i] <= Right[j])
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
L.key[k] = Left[i++];
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
else
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
L.key[k] = Right[j++];
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockEnd.gif)
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void MergeSort(SqList &L, int l, int h)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
![](http://www.cppblog.com/Images/dot.gif)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int low = l, high = h, mid;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if(low < high)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
![](http://www.cppblog.com/Images/dot.gif)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
mid = (low + high) / 2;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
MergeSort(L,low,mid);// the left
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
MergeSort(L,mid + 1, high);// the right
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
Merge(L, low, mid, high);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockEnd.gif)
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockEnd.gif)
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
![](http://www.cppblog.com/Images/dot.gif)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
SqList L;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
L.length = 0;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
while(scanf("%d", &L.key[++L.length]) != EOF)
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
L.length--;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
MergeSort(L, 1, L.length);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for(int i = 1; i <= L.length; i++)
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if(i != L.length)
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
printf("%d ", L.key[i]);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
else
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
printf("%d\n", L.key[i]);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
return 0;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockEnd.gif)
}