归并排序：递归与非递归实现孰优？递归是否不利于编译器？

嘿，很高兴你深入研究了归并排序的两种实现方式，咱们来拆解你的问题和看法～

先看你提到的两种实现代码 #

递归式归并排序 #

#include <stdio.h>
#define MAX 30  // 补充原代码缺失的宏定义以保证编译正常
void merge(int array[], int low, int mid, int 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 array[], int low, int high) {
    int mid;
    if (low != high) {
        mid = (low + high) / 2;
        merge_sort(array, low, mid);
        merge_sort(array, mid + 1, high);
        merge(array, 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()*/

关于“递归实现对编译器不友好”的看法 #

你的观点有一定合理性，但也不用把递归一棒子打死：

• 递归归并排序的递归深度是log₂(n)，比如处理100万元素的数组，递归深度大概只有20层——大多数系统的默认栈空间（几MB）完全能容纳这么小的栈帧，所以普通场景下根本不会出现栈溢出问题。只有处理极端巨大的数组（比如10亿级）时，递归深度才可能达到30层左右，这时候才需要担心栈溢出。
• 编译器对递归的优化确实有限：归并排序的递归不是尾递归（尾递归是指递归调用是函数的最后一个操作，编译器可以把它优化成循环），所以编译器没办法自动把它转换成循环结构，每一层递归都会创建新的栈帧，确实会有一些额外的开销，但这个开销在普通场景下几乎可以忽略。

递归 vs 非递归：哪种实现更好？ #

这完全取决于你的使用场景：

优先选递归的场景 #

• 代码可读性和可维护性：递归代码完全贴合归并排序的分治思想，逻辑清晰到一眼就能看懂，调试和维护起来比非递归简单太多。
• 常规数据规模：如果处理的是百万级以内的数组，递归的栈开销可以忽略，而且递归拆分的子数组更容易被CPU缓存命中，性能甚至不比非递归差。

优先选非递归的场景 #

• 超大数组或受限环境：比如处理十亿级别的数据，或者在嵌入式系统这种栈空间极小的环境下，非递归实现完全不依赖程序栈，能避免栈溢出风险。
• 极致性能优化：如果你的场景对性能要求到了极致，非递归可以省去栈帧创建销毁的开销，虽然差异很小，但确实存在。

总结 #

递归归并非不是“不好的编程方式”，它只是在特定场景下有局限。在大多数日常开发中，递归实现是更优的选择——毕竟代码简洁、易读，出错概率更低。只有当你遇到超大数组或受限环境时，再考虑非递归实现才更合理。

内容的提问来源于stack exchange，提问作者JINU_K