Algorithm（二）：归并排序
归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
归并排序
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。代码实现：
void Merge(int startIndex, int midIndex, int endIndex){int *tmp = (int*) malloc(sizeof(a));if (tmp == NULL){return;}int i = startIndex;int j = midIndex + 1;int k = i;while ((i <= midIndex) && (j <= endIndex)){// = guarantee stable sortingif (a[i] <= a[j]){tmp[k++] = a[i++]; }else{tmp[k++] = a[j++];}}while (i <= midIndex){tmp[k++] = a[i++];}while (j <= endIndex){tmp[k++] = a[j++];}// Write back to a[]i = startIndex;while (i <= endIndex){a[i] = tmp[i++];}free(tmp);// Print Current Arrayint length = sizeof(a) / sizeof(int);for (int i=0; i<length; ++i){printf("%-5d", a[i]);}printf("\n");}void MergeSort(int startIndex, int endIndex){// if startIndex == endIndex, it is one elementif (startIndex < endIndex){int midIndex = startIndex + (endIndex - startIndex) / 2;MergeSort(startIndex, midIndex);MergeSort(midIndex + 1, endIndex);Merge(startIndex, midIndex, endIndex);}}