归并排序C++实现

    #include<iostream>  
    #include<functional>  
    #include<memory>  
    #include<array>  
      
      
    using namespace std;  
      
    const int CNT = 10;  
      
    void merge_sort(array<int,CNT>&,int);  
      
      
    int main()  
    {  
        array<int,CNT> arr = { 1,5,2,4,3,7,9,8,6,0};  
      
        merge_sort(arr,CNT);  
        for (int i = 0; i < 10; i++)  
            cout << arr[i] << endl;  
      
      
        cin.get();  
        return 0;  
    }  
      
      
    void merge_sort(array<int,CNT>& arr,int cont)  
    {  
        function<void(array<int,int,int)> Merge = [&](array<int,CNT>& arr_,int first,int mid,int last)  
        {  
            if (first >= last) //除非第一个和最后一个重合的时候才停止，因为只有两个的时候也需要排序  
            {  
                return;  
            }  
      
      
            Merge(arr_,first,(mid+first) / 2,mid); //递归使左半部分有序  
            Merge(arr_,mid + 1,(mid + 1 + last) / 2,last); //递归使右半部分有序  
      
            //必须把下面的代码放在下面，为了使最后能够处理原先整数组  
            unique_ptr<int[]> temp(new int[last + 1]); //这里的last是实际下标，所以要加1  
            int f = first; //要把first保存一下，最后合并到原数组中时使用  
            int t = mid + 1;  
            int k = 0;  
      
      
      
      
            //直到有一部分全部比较完 注意：要包括最后一个元素  
            while (first <= mid && t <= last)  
            {  
                if (arr[first] < arr[t])  
                {  
                    temp[k++] = arr[first++];  
                }  
                else  
                {  
                    temp[k++] = arr[t++];  
                }  
            }  
      
            //把剩余部分的东西处理完成  
            while (t <= last)  
            {  
                temp[k++] = arr[t++];  
            }  
      
            while (first <= mid)  
            {  
                temp[k++] = arr[first++];  
            }  
      
            //把比较完成的两部分合起来放在原数组中  
            for (int i = 0; i < k; i++)  
            {  
                arr[f + i] = temp[i];  
            }  
        };  
      
        Merge(arr,cont / 2,cont - 1); //中间用cont和cont-1都可，作用只是把最初的数组分为两个  
    }