マージソート - Wikipedia

マージソートの様子 マージソートは、ソートのアルゴリズムで、既に整列してある複数個の列を1個の列にマージする際に、小さいものから先に新しい列に並べれば、新しい列も整列されている、というボトムアップの分割統治法による。大きい列を多数の列に分割し、そのそれぞれをマージする作業は並列化できる。 n個のデータを含む配列をソートする場合、最悪計算量O(n log n)である。分割と統合の実装にもよるが、一般に安定なソートを実装できる。インプレースな（すなわち入力の記憶領域を出力にも使うので、追加の作業記憶領域を必要としない）バリエーションも提案されているが、一般には、O(n)の追加の作業記憶領域を必要とする[1]。 （ナイーブな）クイックソートと比べると、最悪計算量は少ない[1]。ランダムなデータでは通常、クイックソートのほうが速い。 1945年、フォン・ノイマンによって考案された[2]。 基本的な

[n2s]

個人的には「分割する行為も含めて」マージソートと読んでいるのが違和感。大学で読んだ教科書では「ソート済みの列をマージするアルゴリズム」を指していた。分割統治はあくまで応用なのでは？

[pi8027]

安定ソートの一種。クイックソートと同様、分割統治法を使用する。O(n)の外部記憶領域を必要とする。