归并排序

简介

归并排序也是也是基于分治思想是想的算法。归并排序分为两个步骤，首先是对数据进行分区，将数据分为两个部分，两部分分别进行排序，之后再将两个已经排好序的数据集进行合并，归并排序的命名也由此而来。

分治之后的数据如何排序呢，依然是递归的采用归并排序的方式，直到数据集的规模变为1。

过程

归并排序的拆分

归并排序分为两个部分

拆分

归并排序的拆分是典型的递归思想，如果排序的数据集多于1个元素，则将数据集分为两个部分，之后将两个部分递归的进行该操作。

归并

归并是将两个有序的集合合并的过程。

合并的过程如下：

两个集合分别声明初始指针指向集合的头部，比较指针指向的值，较小的值放入结果数组，同时较小值集合的指针往前移动一位，当一个集合提前遍历结束之后，另外一个集合剩余的元素直接放入结果数组的尾部。

C++代码如下：

#include<iostream>
using namespace std;
const int maxn=500000,INF=0x3f3f3f3f;
int L[maxn/2+2],R[maxn/2+2];
void merge(int a[],int n,int left,int mid,int right)
{
    int n1=mid-left,n2=right-mid;
    for(int i=0;i<n1;i++)
        L[i]=a[left+i];
    for(int i=0;i<n2;i++)
        R[i]=a[mid+i];
    L[n1]=R[n2]=INF;
    int i=0,j=0;
    for(int k=left;k<right;k++)
    {
        if(L[i]<=R[j])
            a[k]=L[i++];
        else
            a[k]=R[j++];
    }
}
void mergesort(int a[],int n,int left,int right)
{
    if(left+1<right)
    {
        int mid=(left+right)/2;
        mergesort(a,n,left,mid);
        mergesort(a,n,mid,right);
        merge(a,n,left,mid,right);
    }
}
int main()
{
    int a[maxn],n;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    mergesort(a,n,0,n);
    for(int i=0;i<n;i++)
    {
        if(i)
            cout<<" ";
        cout<<a[i];
    }
    cout<<endl;
    return 0;
}