Pythonでマージソートを実装

マージソートです。併合ソートともいいます。マージソートの基本的な考え方を次図に示します。分割して、順序よく並べ替えることでソートを実現します。

配列xには、[2, 18, 1, 9, 7, 13, 5, 8, 4, 15]という数が並んでいます。これを、前半部と後半部に分割し、[2, 18, 1, 9, 7]と[13, 5, 8, 4, 15]に分けます 。

これを、なんらかの方法でソートします。ソートした結果は[1, 2, 7, 9, 18]と[4, 5, 8, 13, 15]になっているでしょう。その結果をマージしていきます。両者を先頭から順番に睨んでいき、小さいほうを選んで並べていきます。両方とも既に個別にはソートされているので、左から順番に見比べていけばよいということはわかるでしょう。両者をマージし終わった段階で、全体の並べ替えが終了します。

問題は、「なんらかの方法でソート」というところでした。ここで、再帰的な思考が役立ちます。すなわち、半分にしたものもマージソートで並べ替えてしまえばよいだろうという発想です。分割を繰り返していけば、最後は要素が1個になるはずです。そのときは、並べ替えの必要はありません。その1個をそのまま返してあげればよいのです。その処理が再帰の終端条件になります。

マージソートは、分割統治法（divide and conquer algorithm）の一例です。分割統治法とは、問題を部分問題に分けて考えることで容易に解き、それらを統合することで全体を解決しようという考え方です。分割統治法では多くの場合、再帰的に分割統治を行うことで、問題を簡単に解決することを考えます。分割統治法の考え方のマージソートへの応用は、すでに整列している複数個の列を1個の列にマージする際に、小さいものから先に新しい列に並べれば、新しい列も整列されているだろうという考え方に相当します。

なお、マージソートの計算量は、O (n log n)です。データを半分にする処理はO (log n)で実現されるということはこれまで説明してきたとおりで、それぞれの段階でマージする処理は先頭から順番に見ていくだけなのでO (n)です。したがって、全体ではO (n log n)の手数がかかるということがわかります。

マージソートの実装

Pythonでマージソートを実装してみます。プログラムは次のとおりです。バブルソートやビンソートと比べると、多少、複雑になりました。ただし、再帰的定義をしていることに注意さえすれば、理解はさほど難しくないと考えますが、いかがでしょうか。

def merge_sort(x):

  retary = []

  if len(x) <= 1:

    retary.extend(x)

  else:

    m = len(x) // 2

    first = merge_sort(x[:m])

    second = merge_sort(x[m:])

    while len(first) > 0 and len(second) > 0:

      retary.append(first.pop(0) \

        if first[0] < second[0] else second.pop(0))

    retary.extend(first if len(first) > 0 else second)

  return retary

解説を加えます。まず、返り値を戻すための配列を空の配列retaryとして用意しておきます。引数で与えられる変数xの長さが1以下であれば、その配列をextend()でretaryにくっつけてしまいましょう。なお、この処理はlen(x) == 1:としてもほぼ問題ありません。しかし、その条件にするとxに空配列を与えたときにエラーが発生します。そのエラーを回避するために1以下としました。

さて、else: 以降が本体です。まず、対象の配列を真ん中で分割したいので、真ん中のインデクスを求めています。演算子「//」はPython特有のもので、「a // b」はaをbで割った商の整数値をとります。配列xの長さが奇数であるときを配慮したものです。

次のx[:m]とx[m:]も説明が必要でしょう。これはスライスを用いて配列を分割する処理です。前者はxの先頭からm個目までの要素を持つ配列を作り、後者はm番目以降最後までの要素を持つ配列を作ります。したがって、この表記で前半と後半に分割していることになるのです。

再帰的定義でそれらをソートした結果を、配列変数firstとsecondに格納しています。続くwhile文は、それぞれを先頭から順番に眺めて、小さいほうをpop(0)で取り出してretaryに追加していく処理です。どちらかの要素がなくなるまで その処理を続けます。

最後に、残りの要素を追加しています。どちらかの要素がなくなった時点で、片方には要素が残っているはずですが、それは最後に追加した要素よりも大きな要素のみが整列した状態で残っているはずです。したがって、配列の最後にextend()で追加してあげればよいでしょう。while文での処理とこの最後の処理に関しては、三項演算子の「〜 if 条件式 else〜」という記述になっているので少しわかりにくいかもしれませんが、丁寧に追いかけてみればそれほど難しくはないでしょう。

実行例を図に示します。適切に並べ替えが行われていることを確認してください。