2017年7月14日

「マージソート」のやり方を示した画像、ゴミ画像かと思いきや「わかりやすい」「わりといい例なのでは」

まとめました。

ソートアルゴリズムソートプログラミング真アジソートマージソート

kasajimajima
27653
14
118
44
150

わきもと @sidebook37

深夜のゴミ画像 pic.twitter.com/2LFpve5DTC

2017-07-14 01:51:47

拡大

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

まずリストを小さな単位に分け、二つのリストをそれぞれの要素の先頭を比較してマージする。最後までこの操作をくり返すと、リストはソートされている。（上記記事より）