sorting - ソートされたリストとソートされていないリストの両方を含むリストのソートリスト

Question

m 個のソートされていないリスト (0 <=m < k) を含む k 個のリストがあります。リストを、並べ替えも必要な単一の大きなリストにマージするにはどうすればよいですか。並べ替えられるリストに関する情報は提供されていません。

Answer 1

ランダム化されたクイック ソートを使用してソートされていないリストをソートし、マージ ソートを使用してすべてのソート済みリストをマージします。

Answer 2

簡単な答えになる挿入ソートを使用できます。最悪の場合、O(n**2) 自体が実行されます。

それ以外の場合は、ソートされていないリストをソート (マージまたはクイックソート) してマージします。m と k に基づいて、いくつかのマイクロ最適化を行うことができます。ここで、複雑さは n に基づいて O(nlogn) になります。k と m に対応するものを理解できます。