ソートされていない実数の配列を線形時間でソートできますか? これは私が考えていることです：
サイズ n のソートされていない配列が与えられた場合:
- 選択アルゴリズムを使用して要素を見つけ
sqrt(n)^thます (x と呼びます): O(n) - x よりも小さい要素と x よりも大きい要素を見つけて、2 つの配列を形成します: O(n)
- 2 つの配列を別々に並べ替える: O(sqrt(n)log(sqrt(n))) = O(n) as log(n) < sqrt(n)
したがって、アルゴリズム全体は O(n) です
下限が nlog(n) であることはわかっています。私は何を間違っていますか？