Как я могу сделать эффективный алгоритм сортировки слиянием, используя некоторый индекс

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

Я хочу сделать более эффективный метод для настройки 'index'.Как я могу сделать более эффективным выбор некоторого индекса?

Answer 1

Обычная сортировка слиянием делит массив на две равные половины, потому что в общем случае нет более эффективной и простой стратегии.

Но для особых случаев можно использовать естественная сортировка слиянием - он автоматически выбирает схему разбиения на основе набора данных - для частично отсортированных данных это может быть более эффективным - он выбирает последовательности отсортированных элементов и объединяет их без излишней работы для коротких фрагментов.

Возможно, в общем случае стоимость определения таких последовательностей может стать довольно высокой по сравнению с делением на равные части.