C++用递归的方法实现归并排序mergesort（）

解题思路如下：

1、确定数组的大小，以及输入数组中的元素值；

2、将输入的数组进行分组归并；

3、将整个数组分成左右两个数组，左右两个数组再向下分，直至子数组的元素少于2个时，子数组将停止分割；

4、当左右子数组不能再分割，也是都是一个元素时，比较他们的大小，进行排序合并；

5、再排序合并上一级子数组为两个元素的数组，接着再排序合并上一级子数组为四个元素的数组；直至到排序合并刚开始的两个子数组，最后成为拍好序的数组；

具体代码实现如下：

#include<iostream>
using namespace std;
void merge(int array[],int first,int last)
    {
        int temp[last];
        int mid=(first+last)/2;
        int i1=0;
        int i2=first;//the first ele in the left array;
        int i3=mid+1;//the first ele in the right array;
        while(i2<=mid&&i3<=last)//sort the ele of the left array and the right array
        {
            if(array[i2]<array[i3])
                temp[i1++]=array[i2++];
            else
                temp[i1++]=array[i3++];
        }
        while(i2<=mid)//assigning the rest ele of array2 and array3 to temp;
        {
            temp[i1++]=array[i2++];
        }
        while(i3<=last)
        {
            temp[i1++]=array[i3++];
        }
        i1=0;
        while(first<=last)//assign temp to array;
        {
            array[first++]=temp[i1++];
        }    
    }
void mergesort(int data[],int first,int last)
    {
        if(first<last)
        {
            int mid=(first+last)/2;
            mergesort(data,first,mid);
            mergesort(data,mid+1,last);
            merge(data,first,last);
        }
    }    
int main()
{
    int N;
    cin>>N;
    
    int data[N];
    for(int i=0;i<N;i++)
    {
        cin>>data[i];
    }
    
    mergesort(data,0,N-1);
    
    for(int i=0;i<N;i++)
        cout<<data[i]<<" ";    
    return 0;
}