二分归并排序算法_排序算法之归并排序

归并排序（Merge Sort）是一种稳定的、基于比较的排序算法，最坏时间复杂度为 O(nlogn)。其基本思想是将待排序序列分成若干个子序列，每个子序列都是有序的，然后将子序列合并成整体有序的序列。

归并排序的实现方法有两种：自顶向下和自底向上。

自顶向下的归并排序算法实现：

1. 将待排序序列分成两个子序列，分别对这两个子序列进行递归排序。

2. 将两个已经排好序的子序列合并为一个有序序列。

自底向上的归并排序算法实现：

1. 将待排序序列每个元素看成一个独立的有序序列，进行两两合并。

2. 得到 n/2 个长度为 2 的有序序列，再两两合并。

3. 重复步骤 2，直到得到一个长度为 n 的有序序列。

下面是自顶向下的归并排序算法的实现代码（使用了递归）:

void MergeSort(int arr[], int left, int right)
{
    if (left >= right) return;

    int mid = left + (right - left) / 2;
    MergeSort(arr, left, mid);
    MergeSort(arr, mid + 1, right);

    int* temp = new int[right - left + 1];
    int i = left, j = mid + 1, k = 0;
    while (i <= mid && j <= right)
    {
        if (arr[i] <= arr[j])
            temp[k++] = arr[i++];
        else
            temp[k++] = arr[j++];
    }
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= right) temp[k++] = arr[j++];

    for (int p = 0; p < k; p++)
        arr[left + p] = temp[p];

    delete[] temp;
}

下面是自底向上的归并排序算法的实现代码（使用了迭代）：

void MergeSort(int arr[], int n)
{
    int* temp = new int[n];
    for (int len = 1; len < n; len *= 2)
    {
        for (int left = 0; left < n - len; left += len * 2)
        {
            int mid = left + len - 1;
            int right = min(left + len * 2 - 1, n - 1);

            int i = left, j = mid + 1, k = 0;
            while (i <= mid && j <= right)
            {
                if (arr[i] <= arr[j])
                    temp[k++] = arr[i++];
                else
                    temp[k++] = arr[j++];
            }
            while (i <= mid) temp[k++] = arr[i++];
            while (j <= right) temp[k++] = arr[j++];

            for (int p = 0; p < k; p++)
                arr[left + p] = temp[p];
        }
    }
    delete[] temp;
}