对于待排序数组:{ 5, 2, 4, 6, 1, 3, 2, 6 },归并排序的思路如上图,注意上图是从下往上看。

void MergeSortRecursive(int array[], int* buf, int left, int right)
{
    if (left >= right)
        return;

    int mid    = ((right - left) >> 1) + left;
    int left1  = left;
    int right1 = mid;
    int left2  = mid + 1;
    int right2 = right;
    MergeSortRecursive(array, buf, left1, right1);
    MergeSortRecursive(array, buf, left2, right2);

    int i = left;
    while (left1 <= right1 && left2 <= right2)
        buf[i++] = array[left1] < array[left2] ? array[left1++] : array[left2++];

    while (left1 <= right1)
        buf[i++] = array[left1++];
    while (left2 <= right2)
        buf[i++] = array[left2++];

    for (i = left; i <= right; i++)
        array[i] = buf[i];
}

void MergeSort(int array[], int left, int right)
{
    int* buf = new int[right - left + 1];
    MergeSortRecursive(array, buf, left, right);
    delete[] buf;
}

归并排序的时间复杂度很容易计算,为 $O(nlogn)$。

其它

文章开源在 Github - blog-articles,点击 Watch 即可订阅本博客。 若文章有错误,请在 Issues 中提出,我会及时回复,谢谢。

如果您觉得文章不错,或者在生活和工作中帮助到了您,不妨给个 Star,谢谢。

(文章完)

文章作者:刘毅 (Ethson Liu)
发布日期:2019-10-18
原文链接:https://ethsonliu.com/2019/10/merge-sort.html
版权声明:文章版权归本人所有,欢迎转载,但必须保留此段声明,且在文章页面明显位置给出原文链接,否则保留追究法律责任的权利。