c - 使用带有预排序间隔的合并排序

Question

我试图防止对合并排序进行任何不必要的递归调用，因为我的数组是按部分预排序的，例如:

22, 233, 445, 1055, 1, 14, 94, 74545, 75, 134, 323, 9090, 2, 43, 6342, 323452

我正在使用通用的归并排序实现

void merge(int a[], int low, int mid, int high)
{
    int b[10000];
    int i = low, j = mid + 1, k = 0;

    while (i <= mid && j <= high) {
        if (a[i] <= a[j])
            b[k++] = a[i++];
        else
            b[k++] = a[j++];
    }
    while (i <= mid)
        b[k++] = a[i++];

    while (j <= high)
        b[k++] = a[j++];

    k--;
    while (k >= 0) {
        a[low + k] = b[k];
        k--;
    }
}

void mergesort(int a[], int low, int high)
{
    if (low < high) {
        int m = (high + low)/2;
        mergesort(a, low, m);
        mergesort(a, m + 1, high);
        merge(a, low, m, high);
    }
}

如果我的程序知道每 4 个元素已经排序，我如何修改 mergesort 以开始从已排序的 4 个元素组合并，而不是将数组分解为单个元素部分，然后开始合并？

例子:

22,233,445,1055     1,14,94,74545,     75,134,323,9090     2,43,6342,323452
      \                  /                    \                   /
       \                /                      \                 /
   1,14,22,94,233,445,1055,74545        2,43,75,134,323,6342,9090,323452
              \                                           /
               \                                         /
        1,2,14,22,43,75,94,134,233,323,445,1055,6342,9090,74545,323452  

Answer 1

你实现的是Top-down mergesort ，这意味着将数组分成两部分，对每个部分进行排序，然后将它们合并在一起。这是递归完成的。它的问题是，假设数组有 12 个元素，那么它会将数组拆分为 2 个 6 元素数组，这不会利用每 4 个元素已经排序的事实。

您应该改用 Bottom-up mergesort ，即将数组拆分为子数组，每个子数组有4个元素。由于每一个都已经排好序，所以将每两个子数组合并为8元素子数组，再将每两个8元素子数组合并为16元素子数组，以此类推。 N元数组排序代码如下:

for (int sz = 1; sz < N; sz = sz+sz)
    for (int lo = 0; lo < N-sz; lo += sz+sz)
        merge(a, lo, lo+sz-1, min(lo+sz+sz-1, N-1)); 

因为您已经知道每 4 个元素都已排序，所以您可以从 sz 开始，即 4，这样可以充分利用这些知识。