algorithm - 非递归归并排序

Question

谁能用英语解释一下非递归合并排序是如何工作的？

谢谢

Answer 1

非递归合并排序通过考虑输入数组上的窗口大小 1,2,4,8,16..2^n 来工作。对于每个窗口(下面代码中的“k”)，所有相邻的窗口对都合并到一个临时空间中，然后放回数组中。

这是我的单一函数，基于 C 的非递归归并排序。输入和输出在'a'中。 “b”中的临时存储。有一天，我想要一个就地的版本:

float a[50000000],b[50000000];
void mergesort (long num)
{
    int rght, wid, rend;
    int i,j,m,t;

    for (int k=1; k < num; k *= 2 ) {       
        for (int left=0; left+k < num; left += k*2 ) {
            rght = left + k;        
            rend = rght + k;
            if (rend > num) rend = num; 
            m = left; i = left; j = rght; 
            while (i < rght && j < rend) { 
                if (a[i] <= a[j]) {         
                    b[m] = a[i]; i++;
                } else {
                    b[m] = a[j]; j++;
                }
                m++;
            }
            while (i < rght) { 
                b[m]=a[i]; 
                i++; m++;
            }
            while (j < rend) { 
                b[m]=a[j]; 
                j++; m++;
            }
            for (m=left; m < rend; m++) { 
                a[m] = b[m]; 
            }
        }
    }
}

顺便说一句，要证明这是 O(n log n) 也很容易。窗口大小的外层循环增长为 2 的幂，因此 k 有 log n 次迭代。虽然内循环覆盖了很多窗口，但给定 k 的所有窗口加起来正好覆盖了输入数组，因此内循环是 O(n)。合并内循环和外循环:O(n)*O(log n) = O(n log n)。