通信用語の基礎知識 IPv4
戻る
参加者募集中

マージソート

辞書:科学用語の基礎知識 算数・数学編 (NMATH)
読み:マージソート
外語:merge sort 英語
品詞:名詞
2002/12/22 作成
2005/10/31 更新

ソートアルゴリズムの一つ。

すでにソート済みの2つの数列を掛け合わせて新しい1つのソート済み数列を作るという動作を繰り返すことにより実現するソート。

A={2,5,9,11} B={3,5,6,10}という2つのソート済みの数列があるとする。このとき、一番最初の数値(Aは2、Bは3)を比較し、小さいほうである2を取り出し、新しい数列Cに入れる。以下Bの3、Aの5、Bの5、Bの6、Aの9、Bの10、Aの11と取り出していき、数列CはC={2,3,5,5,6,9,10,11}となる。この操作をマージといい、この動作を繰り返すことによってソートができるのである。

最悪計算量がO(n log n)のソートの中では唯一の安定ソートである。しかし、作業領域が必要なため巨大なデータをソートするには適していない。

マージソートの途中経過
5 | 8 | 6 | 1 | 7 | 11 | 5 | 3    初期状態
5   8 | 1   6 | 7   11 | 3   5    1回目のマージ操作
1   5   6   8 | 3   5   7   11    2回目のマージ操作
1   3   5   5   6   7   8   11    3回目のマージ操作
用語の所属
ソート
関連する用語
アルゴリズム
外部ソート
マージ

コメントなどを投稿するフォームは、日本語対応時のみ表示されます


KisoDic通信用語の基礎知識検索システム WDIC Explorer Version 7.03 (16-May-2019)
Search System : Copyright © Mirai corporation
Dictionary : Copyright © WDIC Creators club