排序算法复习（2）——合并排序
合并排序的重点就是怎么原地（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;}