c - ソート済みリストのマージ

Question

4 つの並べ替えられたリストがあり、それらを 1 つの並べ替えられたリストにマージしたいと考えています。
それを行う最も効率的な方法は何ですか？並行して実装できればプラスです。

Answer 1

これはマージソートのマージ部分です。

各リストの先頭にある 4 つの要素の最小値を取得し、出力にダンプします。すべてのリストが空になるまで繰り返します。min4それが固定費である と仮定すると、これは O(N) になります。

より多くの情報 (リストの範囲など) があれば、おそらく少し改善できますが、これらが漸近的な複雑さに影響を与えるとは思いません。