algorithm - 如何通过使用一些索引来制作高效的合并排序算法

Question

我有这样的合并源代码。

void mergesort(low, high){

     index mid;
     if(low < high){
          mid = (low+high)/2;
          mergesort(low mid);
          mergesort(mid+1, high);
          merge(low, mid, high);
    }
}

void merge(low, high, mid){

     index i = low, j = mid +1, k = low;
     while(i<=mid && j<=high){
          if(S[i] < S[j]) {
               U[k] = S[i];
               i++;
          }else{
               U[k] = S[j];
               j++;
          }
          k++;
     }
     if(i > mid){
          copy S[j] through S[high] to U[k] through U[high]
     }else{
          copy S[i] through S[mid] to U[k] through U[high];
     copy U[low] through U[high] to S[low] through S[high];
}

我想制定更有效的方法来调整“索引”。我怎样才能更有效地选择一些指标？

Answer 1

常用归并排序将数组分成相等的两半，因为在一般情况下没有更有效和更简单的策略。

但对于特定情况，可能会使用 natural merge sort - 它根据数据集自动选择拆分方案 - 对于部分排序的数据，它可能更有效 - 它选择排序的元素序列并合并它们，而无需为短片做过多工作。

也许在一般情况下，与划分为等份相比，确定此类序列的成本可能会变得相当高。