はじめに
最近はソートアルゴリズムをいろいろ実装してみています。その流れでマージソートについても実装してみました。
マージソートの概要
対象の配列について大きさが半分になるように二分割してそれぞれに対して再帰的にマージソートを適用し、ソート済みとなったそれぞれをマージして全体をソート済にする、という手順でソートするアルゴリズムです。マージ操作は、それぞれの先頭要素を見て小さい方を取り出して結果用配列に詰める、という操作を繰り返すことで実現します。
要素数が1以下の配列は既にソート済みとみなせるため、その場合は操作を実行しません。これが再帰のベースケース（終了条件）となります。
配列を値の内容によらず単純に二分割していくことから、再帰の深さは必ず$log n$程度に収まります。マージ操作の計算量が$O(n)$なので、全体の計算量が$O(n log n)$になります。最悪のケースでもそうなるのが強いです。また、マージ操作の際に同じ値だったら前のほうを採用するようにすれば安定ソートになります。マージ時に元の配列とは別の配列を使用するため内部ソートではありません。
実装
こちらをKotlinで実装してみます。
ナイーブな実装
まずはあまり高速化などを考えず素直に実装してみます。レシーバがList<Int>のインスタンスで、ソート済の別のインスタンスを返すメソッドとして実装します。
// マージソート
fun List<Int>.mergeSort(): List<Int> {
// 要素数が1以下であればソート済みとみなせる
val list = this
if(list.size < 2) {
return list
}
// 真ん中のインデックス（後ろの先頭）
val middle = list.size / 2
// 左側のソート
val left = list.subList(0, middle).mergeSort()
// 右側のソート
val right = list.subList(middle, list.size).mergeSort()
var i = 0
var j = 0
// ソート結果を格納する配列
val result = mutableListOf<Int>()
// マージ操作
// どちらか片方が空になるまで操作を繰り返す
while (i != left.size && j != right.size) {
// 安定ソートにするため、同じ値だったら左を採用する
if(left[i] <= right[j]) {
result.add(left[i])
i++
} else {
result.add(right[j])
j++
}
}
// 空にならなかったほうの残りを追加していく
while (i != left.size) {
result.add(left[i])
i++
}
while (j != right.size) {
result.add(right[j])
j++
}
return result
}
真ん中（と言いつつ実際には右の先頭）を指すインデックスを求めて、それを元に左側の配列と右側の配列をそれぞれ作って再帰的にマージソートを呼び出します。呼ばれるたびに大きさが半分になっていき、最終的には要素数が1以下になるのでそこで再帰呼び出しが止まります。
マージ操作はどちらかが空になったら一旦止めますが、その後に空とならなかったほうの残りを結果配列に詰める操作を追加で実行します。
（使用される値に制限がある場合は、それを番兵としてもうちょっと短く書けるのですが）
この実装が正しいか確認するため、AtCoderの問題を使ってテストしてみます。
この問題を使います。
提出結果がこちら。問題を解くために使うソートで今回の実装を使っています。
ACと出ていますが、これは正解という意味です。少なくともこの問題で正解できるので、この実装は基本的に正しいはず…
ただ、実行速度とメモリ使用量にはだいぶ改善の余地がありそうです。
もうちょっと最適化した実装
先ほどの実装は再帰呼び出しごとに配列のインスタンスを生成していたことから実効速度が遅くなり、メモリ使用量も増えていたのかと思います。そこで配列のインスタンスを使い回すことで高速化を図ってみます。
以下のような感じです。
ソート結果は元の配列自体を破壊的に変更することで反映してみます。部分ソートができるようにして、再帰呼び出し後も対象の部分だけを書き換えることで配列を別途生成しなくて済むようにします。元の配列とは別にソート結果を一時的に格納する配列は必要ですが、それも一つを使い回すことが可能です。
fun mergeSort(list: MutableList<Int>, start: Int = 0, end: Int = list.size - 1, tmp: MutableList<Int> = MutableList(end - start + 1) {0}) {
val size = end - start + 1
// 要素数が1以下であればソート済みとみなせる
if(size < 2) {
return
}
// 真ん中のインデックス（後ろの先頭）
val middle = size / 2 + start
// 左側のソート
mergeSort(list, start, middle - 1, tmp)
// 右側のソート
mergeSort(list, middle, end, tmp)
var i = start
var j = middle
var k = start
// マージ操作
// どちらか片方が空になるまで操作を繰り返す
// 結果は一旦tmpに詰める
while (i != middle && j <= end) {
// 安定ソートにするため、同じ値だったら左を採用する
if(list[i] <= list[j]) {
tmp[k] = list[i]
i++
} else {
tmp[k] = list[j]
j++
}
k++
}
// 空にならなかったほうの残りを追加していく
while (i != middle) {
tmp[k] = list[i]
i++
k++
}
while (j <= end) {
tmp[k] = list[j]
j++
k++
}
// 最終的な結果は元の配列に書き戻す
for(l in start..end) {
list[l] = tmp[l]
}
}
テスト結果はこちら。
実行速度もメモリ使用量も大きく改善することができました。
なお、MutableListではなくIntArrayを使えばオートボクシング・アンボクシングもなくなってさらに高速化できるはずです。
fun mergeSort(array: IntArray, start: Int = 0, end: Int = array.size - 1, tmp: IntArray = IntArray(end - start + 1)) {
val size = end - start + 1
// 要素数が1以下であればソート済みとみなせる
if(size < 2) {
return
}
// 真ん中のインデックス（後ろの先頭）
val middle = size / 2 + start
// 左側のソート
mergeSort(array, start, middle - 1, tmp)
// 右側のソート
mergeSort(array, middle, end, tmp)
var i = start
var j = middle
var k = start
// マージ操作
// どちらか片方が空になるまで操作を繰り返す
// 結果は一旦tmpに詰める
while (i != middle && j <= end) {
// 安定ソートにするため、同じ値だったら左を採用する
if(array[i] <= array[j]) {
tmp[k] = array[i]
i++
} else {
tmp[k] = array[j]
j++
}
k++
}
// 空にならなかったほうの残りを追加していく
while (i != middle) {
tmp[k] = array[i]
i++
k++
}
while (j <= end) {
tmp[k] = array[j]
j++
k++
}
// 最終的な結果は元の配列に書き戻す
for(l in start..end) {
array[l] = tmp[l]
}
}
いいね！
感想
ヒープソートやクイックソートも書きましたが、
それらに比べるとマージソートのほうが直感的にわかりやすいような気がしました。いろいろ書き比べてみると面白いですね。