归并排序C++实现

学习心得：

其实递归是分治法的天然实现，这点从归并排序上体现得算是淋漓尽致。看看下面这张图里的伪码，思考一下执行过程就会体会到前面这句话。在if满足的时候其实什么实质性的步骤都没有执行，只不过在不停的divide。在if条件满足以后逐层往上调用merge函数进行conquer和combine。

#include <iostream>
using namespace std;

void merge(int arr[], int ll, int m, int r)
{
        int i = ll, j = 0, k = 0;
        int n1 = m-ll+1;
        int n2 = r-m;
        int L[n1], R[n2];

        for (j=0;j<n1;j++)

            L[j]=arr[ll+j];

        for (k=0;k<n2;k++)

            R[k]=arr[m+k+1];
        j = 0, k = 0;
        while(j < n1 && k < n2)
        {
                if(L[j] < R[k])
                arr[i++] = L[j++];
                else
                arr[i++] = R[k++];
        }
        while(j < n1)
        arr[i++] = L[j++];

        while(k < n2)
        arr[i++] = R[k++];
        /*for (i = ll; i<=r; ++i)

        {
          //std::cout <<"in " << "j="<<j << ",k=" << k << std::endl;
          if(j < n1 && k <n2 )
            {
                if(L[j] < R[k])
                arr[i] = L[j++];
                else
                arr[i] = R[k++];
            }
          else
            {
                //std::cout << j << " " << k << std::endl;

                arr[i] = (j>n1 ? R[k++] : L[j++]);                                                                                                                                    

            }                   

              //std::cout << "out"<< "j="<<j << ",k=" << k << std::endl;                                                                                                                 }*/                                                                                                                                                                

}                       

void merge_sort(int a[], int start, int end)
{
        if (start < end)
        {
                int middle = (end + start)/2;
                merge_sort(a, start, middle);
                merge_sort(a, middle + 1, end);
                merge(a, start, middle, end);
        }
}

int main()
{

        int c[] = {3,1,7,5,0,9,2,4,6,8};
        merge_sort(c, 0, 9);
        for(int it:c)
        std::cout <<it << std::endl;
        std::cout <<"============" << std::endl;
        int d[] = {30,11,10,9,8,7,6,5,4,3,2};
        merge_sort(d, 0, 10);
        for(int it:d)
        std::cout <<it << std::endl;
        std::cout <<"============" << std::endl;
        int e[] = {11,10,9,8,7,6,5,4,3,2};
        merge_sort(e, 0, 9);
        for(int it:e)
        std::cout <<it << std::endl;
        std::cout <<"============" << std::endl;
        int b[] = {100, 100, 100, 100,3,5,7,9,10,12};
        merge(b, 4, 6, 9);
        for(int it:b)
        std::cout <<it << std::endl;
        std::cout <<"============" << std::endl;
        int a[] = {1, 3, 5, 7,9,0,2,4,6,8};
        merge(a, 0, 4, 9);
        for(int it:a)
        std::cout <<it << std::endl;
        return 0;
}