算法基础课2归并排序：

归并排序是稳定的,总体是nlogn

第一步：确定分界点mid=(l+r)/2;

第二步：递归排序左边和右边

第三步：归并————合二为一 这个步骤复杂度O(n)

代码：

include[HTML_REMOVED]

using namespace std;
const int N = 1000010;

int n;
int q[N],tmp[N];

void merge_sort(int q[],int l,int r)
{
if(l >= r)return;
mid = l+r >> 1;

merge_sort(q,l,mid);
merge_sort(q,mid+1,r);

int k = 0,i = l,j = mid+1;
while(i<=mid&&j<=r)
if(q[i] <= q[j])tmp[k++] = q[i++];
else temp[k++] = q[j++];

while(i<=mid)temp[k++] = q[i++];
while(j<=r)tmp[k++] = q[j++];

for(i = l,j = 0;i<=r;i++,j++)q[i] = temp[j];

}

int main()
{
scanf(“%d”,&n);
for(int i =0;i<n;i++)scanf(“%d”,&n);

merge_sort(q,0,n-1);

for(int i =0;i<n;i++)printf("%d",q[i]);
return 0;

}