マージソート

マージソートは、ソートのアルゴリズムで、既に整列してある複数個の列を1個の列にマージする際に、小さいものから先に新しい列に並べれば、新しい列も整列されている、というボトムアップの分割統治法による。大きい列を多数の列に分割し、そのそれぞれをマージする作業は並列コンピューティング|並列化できる。n個のデータを含む配列をソートする場合、最悪計算複雑性理論|計算量ランダウの記号|O(n log n)である。分割と統合の実装にもよるが、一般に安定ソート|安定なソートを実装できる。インプレースなソートも提案されているが、通常O(n)の外部記憶を必要とする。（ナイーブな）クイックソートと比べると、最悪計算量は少ない。乱数|ランダムなデータでは通常、クイックソートのほうが速い。