1つの大きなソートされた配列を生成するために、2つの小さなソートされていない配列にマージ操作

Question

最近インタビューで質問されました。
サイズがn+mの配列Aが与えられ、最初にn個の要素がランダムな順序（最後にm個の空白がある場所）で埋められています。また、配列Bはmの要素がランダムな順序であります。

配列Aがソートされた順序で（n + m）の要素で満たされるようにマージ関数を作成します。 私はO((n+m)log(n+m))の溶液を与えることができました。 この問題の解決策がありますか？

Answer 1

noそこには解決策がありません。

t = max(m,n)とすると、複雑さはO(tlog(t))になります。

もっと良い解決策がないことを証明するにはどうすればいいですか？

ウィル何もデータについては知られていないこの問題に対するより良い解決策があった場合は、サイズN (big enough)の任意の配列を指定して、我々は、nにそれを分割しm配列やNlog(N)未満で並べ替えることができます。