什么是归并排序

归并排序（Merge Sort）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略将问题分成一些小的问题然后递归求解，即分而治之。

图解

代码实现

#include<iostream>
using namespace std;
const int maxsize=5;
typedef int datatype;
typedef char othertype;
typedef struct{
    datatype key;
    othertype other;
}rec;
typedef rec list[maxsize+1];
list a;
list b;


void Inser(){
    cout<<"请输入:"<<endl;
    for(int i=1;i<maxsize+1;i++){
        cin>>a[i].other>>a[i].key;        
    }
}


void Merge(list r,list r1,int low,int mid,int high){
    int i,j,k;
    i=low;
    j=mid+1;
    k=low;
    while(i<=mid&&j<=high){
        if(r[i].key<=r[j].key)r1[k++]=r[i++];
        else r1[k++]=r[j++];
    }
    while(i<=mid)r1[k++]=r[i++];
    while(j<=high)r1[k++]=r[j++];
}

void Merge_passage(list r,list r1,int n,int len){
    int i=1;
    while(i+2*len-1<=n){
        Merge(r,r1,i,i-1+len,i-1+2*len);
    }
    if(i-1+len<n){
         Merge(r,r1,i,i-1+len,n);
    }
    else{
        for(int j=i;j<n;j++){
            r1[j]=r[j];
        }
    }
}

void Merge_sort(list r,list r1,int n){
    int len;
    len=1;
    while(len<n){
        Merge_passage(r,r1,n,len);len=len*2;
        Merge_passage(r1,r,n,len);len=len*2;
    }
}

int main(){
    Insert();
    Merge_sort(a,b,maxsize);
    for (int i = 1; i < maxsize + 1; i++) {
		cout << b[i].other << b[i].key << endl;
	}
    return 0;
}