« ^ »

Merge Sort

所要時間: 約 2分

概要

  • ソートのアルゴリズム
  • 既に整列してある複数個の列を1個の列にマージする際に、小さいものから先に新しい列に並べれば、新しい列も整列されている、という分割統治法を用いる。

おおまかな流れ

  1. 分解/結合する
  2. 2つのリストを並べ替える

ポイント(1)

分解/結合する

ー 要素数が1になるまで分解する ー 分解は要素数/2で分解する ー 奇数の時は(要素数-1)/2

ー 並べ替えつつ結合していく ー 結合する順番は分解とは逆の順序で行う

ポイント(2)

2つのリストを並べ替える

  1. 新しいソート済みリストを用意
  2. 2つのリストの先頭同士を比較して小さい方を取り出しソート済みリストに入れる
  3. どちらかのリストが空になるまで2を繰り返す
  4. 余っている方のリストをソート済みリストの後ろにくっつける

サンプルコード (Python)

Pythonの場合

import argparse

def merge(left, right):
    sorted_list = []
    while left and right:
        smaller = left if left[0] < right[0] else right
        sorted_list.append(smaller.pop(0))
        sorted_list.extend(left if left else right)
    return sorted_list

def merge_sort(elms):
    length = len(elms)
    if length <= 1:
        return elms
    else:
        harf = length / 2
        sorted_left = merge_sort(elms[:harf])
        sorted_right = merge_sort(elms[harf:])
        return merge(sorted_left, sorted_right)

def main():
    parser = argparse.ArgumentParser()
    parser.add_argument('-s', dest='sep', default=' ')
    parser.add_argument('--int', dest='int_', default=None, action='store_true')
    opts = parser.parse_args()
    type_ = lambda s: s
    if opts.int_:
        type_ = int
    line = sys.stdin.readline()
    elms = map(type_, map(lambda elm: elm.strip(), line.split(opts.sep)))
    sorted_list = map(str, merge_sort(elms))
    print opts.sep.join(sorted_list)

if __name__ == '__main__':
    main()

実行する

$ chmod 744 merge_sort.py
$ echo 4 1 3 5 6 6 1 9 8 2 | ./merge_sort.py --int
1123456689

特徴

  • 平均計算量 O(n log n)
  • 最悪計算量 O(n log n)
  • 配列にランダムアクセスする必要なし

良いところ

  • そこそこ速い

  • 速い時と遅い時で計算量があまり違わない

    • 平均計算量: O(n log n)

      • 最悪計算量: O(n log n)
  • シーケンシャルアクセスしかできないデータ構造にも使える ex. 連結リストなど

悪いところ

  • ソート済みリストの領域確保が必要配列長の 1/2 のサイズ
  • ランダムアクセスが出来る構造であればクイックソートとかの方が速い