算法解析之归并排序

归并排序

算法思路：
1、将整个序列递归分解为不可分解的单元素序列，这时各个单元素序列有序（递推过程）
2、再将各个单元素序列二路归并（回归过程）

C++：

template <typename T>
void merge(T arr[],int low,int mid,int high){
    //复制到一个临时数组
    T temp[high - low + 1];
    for (int i = low; i <= high; i++) {
        temp[i-low] = arr[i];
    }
    //i和j分别指示两个有序序列的开始
    int i = 0,j = mid + 1 - low;

    //挑出小的归并到arr，同时移动索引，从临时数组中往arr中复制
    for (int k = low; k <= high; k++) {
        //保证索引有效性
        if (i > mid - low) {
            arr[k] = temp[j++];
        }else if (j > high - low){
            arr[k] = temp[i++];
        }else if (temp[i]<temp[j]) {
            arr[k] = temp[i++];
        }else{
            arr[k] = temp[j++];
        }
    }
}
//归并排序
template <typename T>
void mergeSort(T arr[],int low,int high){
    if (high>low) {
        int mid = low + (high - low)/2;
        mergeSort(arr, low, mid);
        mergeSort(arr, mid+1, high);
        merge(arr, low, mid, high);
    }
}