質問に行き詰まっており、一般的な方向性のヒント/ポイントが必要です (答えを求めるのではありません)。
この質問は、ほぼソートされたシーケンスを指定して、時間 O(n) で正しい順序を生成する分割統治アルゴリズムの詳細を求めています。
ほぼソートされているということは、リストが与えられたということです
x_1、x_2、.... x_n
ソートされたリストが
y_1、y_2、... y_n
そして、すべての i、j <= n について、このプロパティが尊重されます。
x_i == y_j && |ij| <= ルート(n)
私の頭に浮かんだ唯一のことは、リストを各レベルでルート（n）グループに分割することでした（これにより、最初の分割では最大でルート（n）の長さになります）が、どこにあるのかよくわかりません再帰的に元に戻すときに、一度に root(n) 個の要素を結合する必要があるためです。
また、再帰の複雑さの方程式は次のようになることもわかりました。
T(n) = ルート(n) * T(n/ルート(n)) + d * ルート(n)
これにより、master's theoremO(n) 時間であることが証明できます。
だから、私は分割で正しい方向に進んでいるように見えますが、特別な方法で分割する必要があるのか 、それとも特定の方法で比較する必要があるのか\u200b\u200bわかりません。
編集：おそらくこれが正しい答えでした。
アルゴリズムは次のとおりです。n > 1 の場合、シーケンスの 2 つの (近似) 半分のそれぞれを再帰的に並べ替えます。これで、すべての要素が正しい位置に配置されました。ただし、中央から √n の位置にある要素を除きます (これが正しい理由がわかりますか?)。そのため、これらの位置の要素をマージします。T(n) を n 個の要素のソートに使用する時間とすると、n > 1 の場合、次のようになります。
T(n)≤2T(⌈n=2⌉) +c * √n
√(n) = n .5および .5 < 1 = log 2 2 なので、分割統治の再帰のマスター定理は、T(n)∈O(n) を教えてくれます。
両方の半分をソートする時間は O( n ⁄ 2 * log( n ⁄ 2 )) であり、結果として O(n*logn) になり、最終的なマージは O(√ n * √n) これは O(n) であり、合計 O(n*logn + n) -> O(n*logn) となります