willcool4ever

void merge(int array[], int start, int mid, int end){
    int i = start;
    int j = mid + 1;
    int k = 0;

    int *tmp = new int[end-start+1] {0};

    while (i<=mid && j<=end) {
        if(array[i] <= array[j])
        {
            tmp[k++] = array[i++];
        }else {
            tmp[k++] = array[j++];
        }
    }
    while (i<=mid) {
        tmp[k++] = array[i++];
    }

    while (j<=end) {
        tmp[k++] = array[j++];
    }

    // 将排序后的元素，将tmp整合到数组a中。
    for (int m=0; m<k; m++) {
        array[start+m] = tmp[m];
    }

    delete [] tmp;

}

// 递归调用函数
void merge_sort_c(int array[], int start, int end)
{
    // 递归终止条件
    if (start >= end) return;

    // 取 start 到 end 之间的中间位置 mid, 并避免整型溢出
    int mid = start + (end - start) / 2;
    // 分治递归
    merge_sort_c(array, start, mid);
    merge_sort_c(array, mid+1, end);
    // 将 A[p...q] 和 A[q+1...r] 合并为 A[p...r]
    // merge(A[p...r], A[p...q], A[q+1...r]);
    // cout<<"("<<p<<"~"<<q<<")"<<" ("<<q+1<<"~"<<r<<")"<<endl;
    merge(array, start, mid, end);
}

// 归并排序算法, A 是数组，n 表示数组大小
void merge_sort(int array[], int size) {
    merge_sort_c(array, 0, size-1);
}

int main()
{
    int array[7] = {10, -22, 211, 120, 23, 120, -2};
    int size = sizeof (array) / sizeof (*array);

    printArray(array, size);

    merge_sort(array, size);

    printArray(array, size);
    return 0;
}
O(nLogn)排序 ：归并

O(nLogn)排序：归并
