Description

归并排序是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列

第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置

第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置

重复步骤3直到某一指针超出序列尾

将另一序列剩下的所有元素直接复制到合并序列尾 

 
#include<bits/stdc++.h>
using namespace std;
int n,a[5000001],b[5000001];//暂存在b[]中
long long ans;
void msort(int l, int r) { //归并排序
	int mid=(l+r)/2;//取中间
	if(l==r) { //若l == r了，就代表这个子序列就只剩1个元素了，需要返回
		return;
	} else {
		msort(l,mid);//分成l和中间一段，中间 + 1和r一段（二分）
		msort(mid+1,r);
	}
	int i=l;//i从l开始，到mid，因为现在排序的是l ~ r的区间且要二分合并
	int j=mid+1;//j从mid + 1开始，到r原因同上
	int t=l;//数组b的下标，数组b存的是l ~ r区间排完序的值
	while(i<=mid&&j<=r) { //同上i，j的解释
		if(a[i]>a[j]) { 
			b[t++]=a[j];//第j个元素比i ~ mid的元素都小，那么第j个元素是目前最小的了，就放进b数组里
			j++;//下一个元素(mid + 1 ~ r的元素小，所以加第j个元素)
		} else {
		   ------
		   ------
		}
	}
	while(----) { //把剩的元素存入 
		b[t++]=a[i];
		i++;
	}
	while(----) { //同理
		b[t++]=a[j];
		j++;
	}
	for(int i=l; i<=r; ++i) { //把有序序列b赋值到a里
		a[i]=b[i];
	}
	return;
}
int main() {
	cin>>n;
	for(int i=1; i<=n; ++i) {
		cin>>a[i];
	}
	msort(1,n);
	return 0;
}

Input Format

一个整数n，再输入n个数

Output Format

从小到大排序后的n个数，每个数以空格格开。

5
1 6 8 7 5

1 5 6 7 8

Source

排序