归并排序——将两个有序表直接归并为一个有序表

归并排序是多次将两个或两个以上的有序表合并成一个新的有序表。最简单的归并是直接将两个有序的子表合并成一个有序的表，即二路归并

二路归并的排序基本思想是：

       将a[0……n-1]看成是n个长度为1的有序序列，然后进行两两归并，得到n/2（向上取整）个长度为2（最后一个有序序列的长度可能为1）的有序序列，再进行两两归并，得到n/4(向上取整)个长度为4（最后一个有序序列的长度可能小于4）的有序序列……直到得到一个长度为n的有序序列

归并排序每趟产生的有序区只是局部有序的，也就是说在最后一趟排序结束前，所有元素并不一定归位了

每次从两个段中取出一个元素进行关键字的比较，将较小者放入c[ ]中，最后将各段余下的部分直接复制到c[ ]中

#include<stdio.h>
#include<iostream>
using namespace std;
//a[]、b[]为需要合并的两个数组，c为合并后的新数组，n为a[]的长度,m为b[]的长度
void merge(int a[],int b[],int c[],int n,int m){
	int i=0,j=0,k=0;//i为a[]的下标，j为b[]的下标,k为c[]的下标	
	//在a[]和b[]均未扫描完时循环
	while(i<n && j<m){
		if(a[i]<=b[j])
		   c[k++]=a[i++];
		else
		   c[k++]=b[j++];
	}
	//如果a[]还有剩余，则将余下部分赋值过去
	while(i<n){
	   c[k++]=a[i++];
	}
	//如果b[]还有剩余，则将余下部分赋值过去
	while(j<m){
	   c[k++]=b[j++];
	}
}
int main(){
  int n,m;//n为a[]的长度,m为b[]的长度
   //初始化
  //数组a[]
  cout<<"n：";
  cin>>n;
  int *a=new int[n];
  cout<<"输入"<<n<<"个数的第一个有序列表：";
  for(int i=0;i<n;i++){
     cin>>a[i];
  }
  //数组b[]
  cout<<"m：";
  cin>>m;
  int *b=new int(m);
  cout<<"输入"<<m<<"个数的第二个有序列表：";
  for(int i=0;i<m;i++){
     cin>>b[i];
  }
  int *c=new int(n+m);//c为合并后的数组
 //归并两个有序列表
  merge(a,b,c,n,m);
  //输出
  cout<<"合并后为："; 
  for(int i=0;i<n+m;i++){
    cout<<c[i]<<" ";
  }
  cout<<endl;
}