学步园

合并排序的重点就是怎么原地（in-place）合并已排序的两个子序列。

关于合并子函数：

（1）写了两个，一个是原地合并；

函数void inplace_merge(/*in-out*/int* a,/*in*/int low,/*in*/int q,/*in*/int high)

（2）一个是非原地合并。

详见函数int merge(/*in*/int* a,/*in*/int n,\
          /*in*/int* b,/*in*/int m,\
          /*in-out*/int* c,/*in*/int k)

原地合并的思想就是：

（1）另外创建两个数组，并把已经排好序的两部分分别拷贝进去；

（2）然后就循环的把两个子序列两面的元素比较，选小的元素赋值给数组a；

循环比较又分三种：

（1）子序列left，right都还没有遍历完，那就比较left和right的值大小，拷贝小的值入a；

（2）子序列left已经遍历完了，right都还没有遍历完；直接拷贝right的值到a

（3）子序列right已经遍历完了，left都还没有遍历完；直接拷贝left的值到a

思路清晰了就可以写了。

另外：

STL里面就有两个算法是将合并已经排序的子序列的：

猛击：merge
 和
inplace_merge

#include <iostream>

#include <cstdlib>
#include <cstdio>
#include <cassert>
#include <vector>
#include <algorithm>


using namespace std;



//int a[N]; n = N
//
void print(/*in*/int* a,/*in*/int n)
{
    assert( a != NULL && n > 0);
    for(int i = 0; i < n; ++i)
    {
        printf("%2d    ",a[i]);
    }
    printf("\n");
}


//sort two sorted list
//
//a[0..n),b[0..m),c[0..k)
int merge(/*in*/int* a,/*in*/int n,\
          /*in*/int* b,/*in*/int m,\
          /*in-out*/int* c,/*in*/int k)
{
    int index_a = 0;
    int index_b = 0;
    int index_c = 0;
    for( ; index_c < k ; ++index_c)
    {
        //
        if( index_a < n && index_b < m )
        {
            if( a[index_a] >= b[index_b] )
            {
                c[index_c] = b[index_b];
                ++index_b;
            }
            else
            {
                c[index_c] = a[index_a];
                ++index_a;
            }
        }
        else if ( index_a >= n && index_b < m)
        {
            c[index_c] = b[index_b];
            ++index_b;
        }
        else if ( index_a < n && index_b >= m )
        {
            c[index_c] = a[index_a];
            ++index_a;
        }
    }//for
}


//a[low..q],a[q+1..r]
//
void inplace_merge(/*in-out*/int* a,/*in*/int low,/*in*/int q,/*in*/int high)
{
    int left_array_size = q - low + 1;//[low,q]
    int left[left_array_size];
    int tmp;
    int i;
    for(tmp = 0,i = low; i <= q; ++i)
    {
        left[tmp++] = a[i];
    }
    //print(left,q-low+1);


    int right_array_size = high - q;//[q+1,high]
    int right[right_array_size];
    for(tmp = 0,i = q + 1; i <= high; ++i)
    {
        right[tmp++] = a[i];
    }
    //print(right,high-q);


    int left_index = 0;
    int right_index = 0;
    int a_index = 0;
    for( a_index = low; a_index <= high ; ++a_index)
    {
        if ( left_index < left_array_size && right_index < right_array_size )
        {
            if ( left[left_index] >= right[right_index])
            {
                a[a_index] = right[right_index];
                right_index++;
            }
            else
            {
                a[a_index] = left[left_index];
                left_index++;
            }
        }
        else if (left_index >= left_array_size && right_index < right_array_size)
        {
            a[a_index] = right[right_index];
            right_index++;
        }
        else if(left_index < left_array_size && right_index >= right_array_size)
        {
            a[a_index] = left[left_index];
            left_index++;
        }
    }


}


//a[low..high]
//if we have an array ,int a[100];
//then call merge_sort(a,0,99),NOT merge_sort(a,0,100)
//
void merge_sort(/*in-out*/int* a,/*in*/int low,/*in*/int high)
{
    if ( low >= high )
        return;
    int q = (low + high)/2;
    merge_sort(a,low,q);
    merge_sort(a,q+1,high);
    inplace_merge(a,low,q,high);
}


int main()
{
    int a[] = {99,-99,63,72,10,24,888,10,89,56,40,17,68};
    const int ARRAY_SIZE = sizeof(a)/sizeof(*a);
    merge_sort(a,0,ARRAY_SIZE-1 );
    print(a,ARRAY_SIZE);
    cout << endl;


    return 0;
}