algorithm - 如何通过使用一些索引来进行有效的合并排序算法

我有这样的合并源代码。

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];
}

我想用更有效的方法来调整索引如何才能更有效地选择索引？

最佳答案

常用的合并排序将数组分成两等分，因为通常情况下没有更有效和更简单的策略。
但对于特定情况，可以使用natural merge sort-它根据数据集自动选择拆分方案-对于部分排序的数据，它可能更有效-它选择排序的元素序列并合并它们，而不必为短片段做过多的工作。
也许在一般情况下，确定这种序列的成本可能会变得相当高，而不是划分成相等的部分。

关于algorithm - 如何通过使用一些索引来进行有效的合并排序算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/52960161/