マージソート
初期データ: 8 4 3 7 6 5 2 1
データ列を二分割する。 8 4 3 7 | 6 5 2 1
もう一度、二分割する。 8 4 | 3 7 | 6 5 | 2 1
各データ列にデータ数が2以下になったところで、各データ列内のデータをソートする。 4 8 | 3 7 | 5 6 | 1 2
この例の場合は、右2つのデータ列、左2つのデータ列をそれぞれマージとソートし、2つのデータ列にする。 3 4 7 8 | 1 2 5 6
2つのデータ列をマージとソートする。 1 2 3 4 5 6 7 8