c - 合并排序的更好方法是什么？递归函数还是非递归函数？

Question

我在搜索归并排序时发现了两种函数。

第一个是像这样使用递归。

#include <stdio.h>

void merge(array, low, mid, high) {
    int temp[MAX];
    int i = low;
    int j = mid + 1;
    int k = low;

    while ((i <= mid) && (j <= high)) {
        if (array[i] <= array[j])
            temp[k++] = array[i++];
        else
            temp[k++] = array[j++];
    }/*End of while*/

    while (i <= mid)
        temp[k++] = array[i++];

    while (j <= high)
        temp[k++] = array[j++];

    for (i = low; i <= high; i++)
        array[i] = temp[i];

}/*End of merge()*/

void merge_sort(int low, int high) {
    int mid;
    if (low != high) {
        mid = (low + high) / 2;
        merge_sort(low, mid);
        merge_sort(mid + 1, high);
        merge(low, mid, high);
    }
}/*End of merge_sort*/

然后，我认为递归函数不适用于大型数组。在这种情况下，此函数会导致大量递归调用。我认为这是一种糟糕的编程方式。 (其实我不喜欢递归。)

所以，我找到了另一种方法，一个没有递归的合并排序函数:

#include <stdio.h>

#define MAX 30

int main() {
    int arr[MAX], temp[MAX], i, j, k, n, size, l1, h1, l2, h2;

    printf("Enter the number of elements : ");
    scanf("%d", &n);

    for (i = 0; i < n; i++) {
        printf("Enter element %d : ", i + 1);
        scanf("%d", &arr[i]);
    }

    printf("Unsorted list is : ");
    for (i = 0; i < n; i++)
        printf("%d ", arr[i]);

    /* l1 lower bound of first pair and so on */
    for (size = 1; size < n; size = size * 2) {
        l1 = 0;
        k = 0;  /* Index for temp array */
        while (l1 + size < n) {
            h1 = l1 + size - 1;
            l2 = h1 + 1;
            h2 = l2 + size - 1;
            /* h2 exceeds the limlt of arr */
            if (h2 >= n) 
                h2 = n - 1;

            /* Merge the two pairs with lower limits l1 and l2 */
            i = l1;
            j = l2;

            while (i <= h1 && j <= h2) {
                if (arr[i] <= arr[j])
                    temp[k++] = arr[i++];
                else
                    temp[k++] = arr[j++];
            }

            while (i <= h1)
                temp[k++] = arr[i++];
            while (j <= h2)
                temp[k++] = arr[j++];

            /** Merging completed **/
            /*Take the next two pairs for merging */
            l1 = h2 + 1; 
        }/*End of while*/

        /*any pair left */
        for (i = l1; k < n; i++) 
            temp[k++] = arr[i];

        for (i = 0; i < n; i++)
            arr[i] = temp[i];

        printf("\nSize=%d \nElements are : ", size);
        for (i = 0; i < n; i++)
            printf("%d ", arr[i]);

    }/*End of for loop */

    printf("Sorted list is :\n");
    for (i = 0; i < n; i++)
        printf("%d ", arr[i]);

    printf("\n");

    return 0;
}/*End of main()*/

我认为这比使用递归要好。此函数将递归减少为一系列 for 和 while 循环!当然，他们的行为有所不同。我认为递归函数对编译器不利。我说得对吗？

Answer 1

假设优化实现，迭代自下而上合并排序比递归自上而下合并排序要快一些，因为它跳过了索引的递归生成。对于较大的数组，自上而下的额外开销相对较小，O(log(n))，与 O(n log(n)) 的总时间相比，在这两种情况下，大部分时间都花在执行合并上，这可以自下而上和自上而下是相同的。自顶向下合并排序使用 O(log(n)) 堆栈空间，而两者都使用 O(n) 工作空间。然而，几乎所有稳定排序的库实现都是迭代自下而上归并排序的一些变体，例如插入排序和自下而上归并排序的混合体。

链接到显示优化的自上而下合并排序的答案，使用一对相互递归的函数来控制合并方向以避免数据复制:

Mergesort implementation is slow

答案链接包括快速排序、2 向自下而上归并排序和 4 向自下而上归并排序:

Optimized merge sort faster than quicksort