C++でのマージソートの最悪のケースを引き起こす順列を見つけます

要素のセットがあるとします。これらの要素のどの順列がマージソートの最悪の場合になるかを見つける必要がありますか？漸近的にわかるように、マージソートは常にO（n log n）時間を消費しますが、場合によっては、より多くの比較が必要になり、より多くの時間が消費されます。ここでは、典型的なマージソートアルゴリズムを実装してソートするときに、より多くの比較を必要とする入力要素の順列を見つける必要があります。

したがって、入力が[11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26]の場合、出力は[11,19 、15、23、13、21、17、25、12、20、16、24、14、22、18、26]。

これを解決するには、次の手順に従います-

• 関数merge（）を定義します。これには、配列arr、配列left、配列right、l_index、m_index、r_index、
が必要です。
• iを初期化する場合：=0、i <=m_index --l_indexの場合、更新（iを1増やします）、実行-
  • arr [i]：=left [i]
• jを初期化する場合：=0、j
• arr [i + j] =right [j]

例

理解を深めるために、次の実装を見てみましょう-

#include <bits/stdc++.h>
using namespace std;
void display(int A[], int size) {
   for (int i = 0; i < size; i++)
      cout << A[i] << " ";
   cout << endl;
}
int merge(int arr[], int left[], int right[],int l_index, int m_index, int r_index) {
   int i;
   for (i = 0; i <= m_index - l_index; i++)
      arr[i] = left[i];
   for (int j = 0; j < r_index - m_index; j++)
      arr[i + j] = right[j];
}
int divide(int arr[], int left[], int right[], int l_index, int m_index, int r_index) {
   for (int i = 0; i <= m_index - l_index; i++)
      left[i] = arr[i * 2];
   for (int i = 0; i < r_index - m_index; i++)
      right[i] = arr[i * 2 + 1];
}
int gen_worst_seq(int arr[], int l_index, int r_index) {
   if (l_index < r_index) {
      int m_index = l_index + (r_index - l_index) / 2;
      int left[m_index - l_index + 1];
      int right[r_index - m_index];
      divide(arr, left, right, l_index, m_index, r_index);
      gen_worst_seq(left, l_index, m_index);
      gen_worst_seq(right, m_index + 1, r_index);
      merge(arr, left, right, l_index, m_index, r_index);
   }
}
int main() {
   int arr[] = {11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26};
   int n = sizeof(arr) / sizeof(arr[0]);
   gen_worst_seq(arr, 0, n - 1);
   display(arr, n);
}

入力

11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26

出力

11 19 15 23 13 21 17 25 12 20 16 24 14 22 18 26