Rubyでマージソートを徹底解説！分割統治と再帰で学ぶ効率的なソートアルゴリズム

本記事は、Rubyでさまざまなソートアルゴリズムを実装するシリーズの第3回です。第1回ではバブルソート、第2回では選択ソートについて取り上げました。

これまでの連載でも触れてきたように、データをどう並べ替えるかを理解することは、ソフトウェアエンジニアにとって欠かせないスキルのひとつです。幸いなことに、Rubyのような高水準言語には、配列を効率的にソートできる組み込みメソッドがすでに備わっています。たとえば、配列に対して .sort を呼び出すと、内部ではクイックソートが使われています。本記事では、クイックソートとよく似たアルゴリズムである「マージソート」について学んでいきます。この2つはどちらも「分割統治（divide and conquer）」というアプローチを採用しています。マージソートは1945年にジョン・フォン・ノイマンによって考案されました。彼は著名なコンピュータ科学者・物理学者であり、マンハッタン計画への参画や「ミニマックス定理」、モンテカルロ法などの業績でも知られています。

大まかに説明すると、マージソートは配列を2つの部分配列へ繰り返し分割し（再帰を利用）、要素が1つだけ残る状態まで処理を進めます。その後、要素を「マージ（結合）」しながら戻して、最終的なソート済み配列を作り上げます。バブルソートなど他のアルゴリズムと異なり、マージソートは視覚化なしでは理解が難しいアルゴリズムです。以下の図は、Wikipediaのマージソートの動作を段階的に示したイラストです。まだ仕組みがぼんやりしていても心配いりません。この後、実際のコードを一緒に見ていきましょう。

これまで扱ってきたバブルソートや選択ソートは、実務ではほぼ使い物になりませんでしたが、マージソートはBig-O記法の観点で見るとはるかに優れたパフォーマンスを発揮します。Big-O記法をご存じない方のために簡単に説明すると、これはアルゴリズムの最悪ケースの性能を表す指標で、アルゴリズム同士を容易に比較できます。たとえば、Big-OがO(1)のアルゴリズムは、要素数「n」が増えても最悪実行時間が一定であることを意味します。一方、O(n)のアルゴリズムは、nの増加に比例して最悪実行時間が直線的に伸びます。つまり、100個の要素を持つ配列をソートする際にO(n)とO(1)のアルゴリズムを選べるなら、O(1)の方が確実に速いため、こちらを選ぶべきです。バブルソートと選択ソートはどちらも最悪ケースでO(n²)となり、要素数が増えるほど極端に遅くなるため、実用性が低いと言えます。対照的に、マージソートはn log nで動作するため、バブルソートや選択ソートほど効率を犠牲にしません。

それでは、図の例を順番に追ってみましょう。まず [38, 27, 43, 3, 9, 82, 10] という配列から始めて、要素が1つになるまで半分ずつに分割していきます。

1. 最初の配列を2つに分割します：[38, 27, 43, 3] と [9, 82, 10]。
2. 前半をさらに分割します：[38, 27] と [43, 3]。
3. 単一要素まで分割します：[38]、[27]、[43]、[3]。
4. 38と27をソートして [27, 38] を作り、43と3をソートして [3, 43] を作ります。
5. これらをまとめると、[3, 27, 38, 43] になります。
6. 次に、元の配列の後半である [9, 82, 10] に移ります。半分に分割すると [9, 82] と [10] になります。
7. [9, 82] を [9] と [82] に分割します。[10] はすでに単一要素です。
8. [9, 82] をソートして戻し、[10] をマージすると、[9, 10, 82] になります。
9. 最後に、[3, 27, 38, 43] と [9, 10, 82] をマージして、[3, 9, 10, 27, 38, 43, 82] が完成します。

Rubyでの実装例

以下は、Rubyで書かれたマージソートのアルゴリズムです。

class MergeSort
  def sort(numbers)

    num_elements = numbers.length
    if num_elements <= 1
      return numbers
    end

    half_of_elements = (num_elements / 2).round

    left  = numbers.take(half_of_elements)
    right = numbers.drop(half_of_elements)

    sorted_left = sort(left)
    sorted_right = sort(right)

    merge(sorted_left, sorted_right)
  end

  def merge(left_array, right_array)
    if right_array.empty?
      return left_array
    end

    if left_array.empty?
      return right_array
    end

    smallest_number = if left_array.first <= right_array.first
      left_array.shift
    else
      right_array.shift
    end

    recursive = merge(left_array, right_array)

    [smallest_number].concat(recursive)
  end
end

それでは、このコードの流れを順番に確認しましょう。まずは冒頭の sort メソッドに注目します。

  def sort(numbers)

    num_elements = numbers.length
    if num_elements <= 1
      return numbers
    end

    half_of_elements = (num_elements / 2).round

    left  = numbers.take(half_of_elements)
    right = numbers.drop(half_of_elements)

    sorted_left = sort(left)
    sorted_right = sort(right)

    merge(sorted_left, sorted_right)
  end

この部分の目的は、与えられた数値の配列を、各要素が1つだけ残るまで半分に分割し続けることです。動作を確認したい場合は、最終行の merge(sorted_left, sorted_right) をコメントアウトし、代わりに sorted_left と sorted_right を出力してみてください。サンプルの配列を渡してプログラムを実行すると、ターミナルには次のように表示されます。

merge_sort = MergeSort.new
puts merge_sort.sort([38, 27, 43, 3, 9, 82, 10])

ruby ruby-merge-sort.rb

27
43
38

3
9
82
10

うまくいきましたね。コードが初期の配列を受け取って、正しく半分に分割できています。次に、コードの merge 部分を見ていきましょう。

  def merge(left_array, right_array)
    if right_array.empty?
      return left_array
    end

    if left_array.empty?
      return right_array
    end

    smallest_number = if left_array.first <= right_array.first
      left_array.shift
    else
      right_array.shift
    end

    recursive = merge(left_array, right_array)

    [smallest_number].concat(recursive)
  end

まず、いずれかの部分配列が空かどうかを判定します。空であれば、もう一方をそのまま返します。両方とも空でなければ、各配列の先頭要素を比較し、shift で比較済みの要素を取り除くことで無限ループを防ぎます。その後、元の配列に対して再帰処理（すぐ後で解説します！）を適用し、最終的に2つの配列をソート済みの状態で美しく結合します。

再帰についてもう少し詳しく

このコードの中で「？」と思う箇所があるとすれば、おそらくこの行でしょう：recursive = merge(left_array, right_array)。メソッド自身の中から merge を呼び出しています。これこそが「再帰」です。再帰とは、特定の条件が満たされるまで関数が自分自身を1回以上呼び出し続けるテクニックのことです。今回の場合、左右どちらかの配列が空になるまで merge が呼び続けられます。再帰をもっと深く学びたい方は、Rubyの再帰を使ってフィボナッチ数列を求める関数を実装するチュートリアルも参考になるので、ぜひチェックしてみてください。

まとめ

マージソートについて楽しんで学べたなら幸いです。大まかな仕組みを理解し、バブルソートや選択ソートよりもなぜ効率的なのかを把握しておくことは、技術面接や日常業務で必ず役立ちます。また、マージソートには多数の派生形が存在するため、興味があればWikipediaでさらに調べてみるのもおすすめです。それでは次回まで……ハッピーソーティング！