algorithm - 2 つのリストを並べ替えてから結合する必要がありますか、それとも逆にする必要がありますか?

Question

数字のリストが 2 つある場合、並べ替えられた 1 つのリストを取得するには、最初に個々のリストを並べ替えてからマージ ソートを行うか、2 つのリストを 1 つのリストに結合してから効率的な並べ替えアルゴリズムを適用する必要があります。 ?

Answer 1

どちらの方法でも議論できます。それは多くの要因に依存します:

リスト A と B のオプションは次のとおりです。

1. sort(A concat B)
2. マージ (並べ替え (A)、並べ替え (B))

A と B の両方がほぼソートされており、サイズが類似している場合、挿入ソートなど、ほぼソートされたリストで高速に動作することを両方で行うことができます。次に、線形時間を要するマージを実行し、オプション (2) をほぼ線形にします。ただし、この場合、各リスト内の値の範囲が類似している場合、オプション (1) はまったく適切ではなく、値が基数またはカウントに対応していないと仮定すると、おそらく O(n log n) になります。選別。つまり、多くの並べ替えアルゴリズムでは、データが長距離にわたって移動されるため、長いリストは悪影響を及ぼします。

これで、おそらくオプション (1) の方が優れているケースを思いつくことができます。

ただし、オプション (2) が常に適切であることがわかった場合でも、単純に再帰的な分割とマージのアプローチを適用する必要があるという意味ではありません。そうするとオーバーヘッドが発生するからです。

しかし、「どのソート方法が優れているか」に関するすべての質問と同様に、実際に確認する必要があるのは次のとおりです。

• リストのサイズ
• リスト内の値の範囲 (最小、最大) (特定の状況では O(n) ソートを使用できるため)
• それらがほぼソートされているか、ほぼ逆ソートされているか、完全にランダムであるか、またはその他のものであるかどうか
• 外部メモリの許可、禁止など。
• メモリ内でソートするか、ファイルをソートするか
• リストがほぼ同じサイズであるか、一方が他方よりもはるかに長いか。

要するに、「場合による」のですが、リストが既に分割されていて、並べ替えアルゴリズムがリストの長さに敏感な場合は、オプション (2) から何らかの利点を得ることができます。

Answer 2

それらがまだソートされていない場合は、それらを結合して単一のソートを行います。それらを個別にソートしてからマージソートを実行する方が効率的である場合、最も効率的なソートアルゴリズムはそのように構築されます。リストを任意に2つに分割し、個別にソートしてマージします。しかし、そうではありません。