Merge Sort 2种不同写法的比较

Question

我最近学习了 C++ 中的合并排序算法，并在教程中遇到了 2 种不同的实现方法。

第一种方式：

void merge(int arr[], int low, int mid, int high) {
    const int n1 = (mid - low + 1);
    const int n2 = (high - mid);
    int *a = new int[n1], *b = new int[n2];//dynamically allocated because of MSVC compiler
    for (int i = 0; i < n1; i++)
        a[i] = arr[low + i];
    for (int i = 0; i < n2; i++)
        b[i] = arr[mid + 1 + i];
    int i = 0, j = 0, k = low;
    while (i < n1 && j < n2) {
        if (a[i] < b[j]) {
            arr[k] = a[i];
            i++;
        } else {
            arr[k] = b[j];
            j++;
        }
        k++;
    }
    while (i < n1) {
        arr[k] = a[i];
        k++, i++;
    }
  
    while (j < n2) {
        arr[k] = b[j];
        k++, j++;
    }
    delete[] a;
    delete[] b;
}

void mergeSort(int arr[], int start, int end) {
     if (start < end) {
        int mid = (start + end) / 2;
        mergeSort(arr, start, mid);
        mergeSort(arr, mid + 1, end);
        merge(arr, start, mid, end);
    }
}

int main() {
    int arr[] = { 9, 14, 4, 8, 6, 7, 5, 2, 1 };
    unsigned size = sizeof(arr) / sizeof(arr[0]);
    printArray(arr, size);
    mergeSort(arr, 0, size - 1);
    printArray(arr, size);
    return 0;
}

第二种方式：

使用在参数中传递的 temp 数组。

void merge(int arr[], int temp[], int low, int mid, int high) {
    int i = low, k = low, j = mid + 1;
    while (i <= mid && j <= high) {
        if (arr[i] < arr[j]) {
            temp[k] = arr[i];
            i++;
        } else {
            temp[k] = arr[j];
            j++;
        }
        k++;
    }
    while (i <= mid) {
        temp[k] = arr[i];
        k++, i++;
    }
    while (j <= high) {
        temp[k] = arr[j];
        k++, j++;
    }
    for (int i = low; i <= high; i++)
        arr[i] = temp[i];
}

void mergeSort(int arr[], int temp[], int start, int end) {
    if (start < end) {
        int mid = (start + end) / 2;
        mergeSort(arr, temp, start, mid);
        mergeSort(arr, temp, mid + 1, end);
        merge(arr, temp, start, mid, end);
    }
}

int main() {
    int arr[] = { 9, 14, 4, 8, 6, 7, 5, 2, 1 };
    unsigned size = sizeof(arr) / sizeof(arr[0]);
    int *buffer = new int[size];
    printArray(arr, size);
    mergeSort(arr, buffer, 0, size - 1);
    printArray(arr, size);
    delete[] buffer;
    return 0;
}

printArray方法：-

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

合并排序哪种写法更好更快？

Answer 1

一次性分配临时数组并将其作为参数传递比在每次合并调用时分配临时数组实例要快得多。

旁注 - 几乎所有稳定排序的库实现都是某种类型的混合插入排序 + 自底向上合并排序，例如 TimSort。自上而下的合并排序主要用于课堂，而不是图书馆的实际实施。

Answer 2

第二个实现只分配一次辅助内存并递归地传递指针，而第一个实现在每次合并调用时调用一次分配器和释放器。对于大型数组，第二个代码可能比第一个更快。

但是请注意，这两个代码都有问题：

他们使用 int 作为索引变量，将数组的长度限制为 INT_MAX，这小于当前硬件的能力。
将 mid 计算为 int mid = (start + end) / 2;，这会导致大于 INT_MAX / 2 的数组发生算术溢出，从而导致未定义的行为并可能崩溃。 mid 应该这样计算：int mid = start + (end - start) / 2;
他们分配了太多内存：第二个临时数组在第一个代码中没有用，临时数组的大小可能是第二个代码的一半。
他们复制了太多数据：复制下半部分的剩余部分没有用，因为这些元素已经存在。
它们没有实现稳定排序：元素应该与 arr[i] <= arr[j] 而不是 arr[i] < arr[j] 进行比较。
自上而下的递归合并排序算法不是最优的：自下而上的合并排序实现通常更有效，切换到小块的插入排序往往会提高性能，而对排序子范围的测试会进一步提高实际情况下的性能。

Merge Sort 2种不同写法的比较

Comparison between 2 different ways of writing Merge Sort

c++

mergesort

compare