クイックリファレンス

マージソートは、アイテムのリストをソートするための便利なアルゴリズムです.それは効率的で予測可能なアルゴリズムです.あなたの中に必然的に来るinterviews , いずれかを直接要求されるか、またはコードの挑戦を解決するために便利でしょう.これはマージソートのクイックリファレンスです.

アルゴリズム設計
マージソートは、ソートされていないリストを受け取り、ソートされたバージョンを生成する再帰アルゴリズムです.
これは安定したソートアルゴリズムです.
分割および征服アルゴリズムは、入力を半分に分割し、両側をソートし、結果を結合します.

Merge-Sort( input )
    if length( input ) < 1
        return input

    left-half, right-half = divide-in-half( input )
    left = Merge-Sort( left-half )
    right = Merge-Sort( right-half )

    out = []
    while not empty left or not empty right
        if front( left ) < front( right )
            out.append( pop-front(left) )
        else
            out.append( pop-front(right) )

参照sample code in Python .

アルゴリズム複雑度
アルゴリズムのスタック深さlog N . これはどれだけ深く再帰的な呼び出しですMerge-Sort 入れ子になっている.これらのレベルの各々で、それは半分の入力サイズを持ちます、しかし、呼び出しは二回されます.したがって、すべての呼び出し全体で、各レベルで効果的に、全体の入力が動作します.これは複雑さに役立ちます.
マージソートアルゴリズムの複雑さは入力に依存しません.最悪ケースの複雑さは最良のケース複雑さと同じである.常に同じ数の比較を行い、同じ数のコピーを作る.

時間:比較
比較の数は、2つのアイテムを比較した回数を比較します.これは通常、< 比較.
それぞれのlog n 再結合する必要がある再帰的なレベルn 比較.これはθ(n · log n) 比較.

時:コピー
コピーの数は、アイテムが新しい場所にコピーされる回数です.
それぞれのlog n 再帰レベルn 再結合時に新しい出力配列に項目をコピーします.これはθ(n · log n) コピー.
初期の分裂は同じ量のコピーをするかもしれません.これは実際の条件でコピー時間を2倍にしますが、上限を変えません.これは言語依存であり、分割段階でコピーを避けるために入力にビューを使用することが可能です.

スペース
各レベルは、新しいリストに要素を結合する必要があるように、再帰の各レベルは、入力のコピーが必要です.これはθ(n · log n) スペース.

ノート
マージソートは、リンクリストや配列などの複数のコンテナ型に適した要素へのランダムアクセスを必要としません.
これは、すべてのデータを同時にメモリ内にする必要があります外部のソートを可能にします.

View my video class that covers the design, complexity, and code of the algorithm.