歸并排序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, CNT>&, 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, 0, cont / 2, cont - 1); //中間用cont和cont-1都可，作用只是把最初的數組分為兩個  
    }