使用带有预分隔间隔的mergesort

Question

我试图阻止任何不必要的递归调用mergesort,因为我的数组是由部分预分类,例如:

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

我正在使用通用mergesort实现

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

What you implemented is Top-down mergesort, which means to split the array into two parts, sort each, and merge them together. This is done recursively. The problem of it is, assuming the array has 12 elements, then it would split the array into 2 6-element arrays, that would take no advantage of the fact that every 4 elements are already sorted.

You should instead use Bottom-up mergesort, that is, split the array into subarrays, each of the subarrays have 4 elements. Since each of them are already sorted, merge every two subarrays into 8-element subarrays, and then merge every two 8-element subarrays into 16-element subarrays, and so on. The code of sorting N-element array is like this:

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)); 

Since you already know that every 4 elements are sorted, you can start with sz being 4, which takes full advantage of the knowledge.