1.はじめに

このチュートリアルでは、マージソートアルゴリズムとそのJavaでの実装について見ていきます。

マージソートは最も効率的なソート手法の1つであり、「分割統治」パラダイムに基づいています。

2.アルゴリズム

  • マージソートは、最初に問題を部分問題に分割する「分割統治」アルゴリズムです。

これは、主な問題ではなく部分問題を扱うときに再帰を使って簡単に実装できるアルゴリズムの1つです。

このアルゴリズムは、次の2段階のプロセスとして記述できます。

  • ** Divide:このステップでは、入力配列を2つの半分に分割します。

ピボットは配列の中点です。このステップは、分割するハーフアレイがなくなるまで、すべてのハーフアレイに対して再帰的に実行されます。


  • 征服者:このステップでは、分割した配列を

    からソートしてマージします

下から上に並べ替え、ソートされた配列を取得します。

次の図は、配列\ {10、6、8、5、7、3、4}の例に対する完全なマージソートプロセスを示しています。

ダイアグラムをよく見ると、サイズが1になるまで配列が2つの半分に再帰的に分割されていることがわかります。サイズが1になると、マージプロセスが実行され、ソート中に配列のマージを再開します。

リンク:/uploads/mergesort1-100×87.png%20100w[]

3.実装

実装のために、

入力配列とその長さ

をパラメータとして取る

mergeSort

関数を書きましょう。これは再帰関数なので、基底条件と再帰条件が必要です。

基本条件は、配列の長さが1であるかどうかを確認し、それが返されるだけです。それ以外の場合は、再帰呼び出しが実行されます。

  • 再帰的なケースでは、中央のインデックスを取得し、2つの一時配列

    l[]

    と

    r[]

    ** を作成します。その後、

    mergeSort

    関数が両方のサブ配列に対して再帰的に呼び出されます。 

public static void mergeSort(int[]a, int n) {
    if (n < 2) {
        return;
    }
    int mid = n/2;
    int[]l = new int[mid];
    int[]r = new int[n - mid];

    for (int i = 0; i < mid; i++) {
        l[i]= a[i];
    }
    for (int i = mid; i < n; i++) {
        r[i - mid]= a[i];
    }
    mergeSort(l, mid);
    mergeSort(r, n - mid);

    merge(a, l, r, mid, n - mid);
}

  • 次に、入力と両方のサブ配列、および両方のサブ配列の開始インデックスと終了インデックスを受け取る

    merge

    関数を呼び出します。


  • merge

    関数は両方の部分配列の要素を一つずつ比較し、小さい方の要素を入力配列に入れます。

一方の部分配列の終わりに達すると、もう一方の配列の残りの要素が入力配列にコピーされ、最終的なソート済み配列が得られます。 

public static void merge(
  int[]a, int[]l, int[]r, int left, int right) {

    int i = 0, j = 0, k = 0;
    while (i < left && j < right) {
        if (l[i]<= r[j]) {
            a[k++]= l[i++];
        }
        else {
            a[k++]= r[j++];
        }
    }
    while (i < left) {
        a[k++]= l[i++];
    }
    while (j < right) {
        a[k++]= r[j++];
    }
}

プログラムの単体テスト: 

@Test
public void positiveTest() {
    int[]actual = { 5, 1, 6, 2, 3, 4 };
    int[]expected = { 1, 2, 3, 4, 5, 6 };
    MergeSort.mergeSort(actual, actual.length);
    assertArrayEquals(expected, actual);
}

4.複雑さ

マージソートは再帰的アルゴリズムであるため、時間の複雑さは次の再帰的関係として表すことができます。 

T(n) = 2T(n/2) + O(n)


2T（n/2）

はサブアレイのソートに必要な時間、

O（n）

はアレイ全体をマージするのに必要な時間です。

解決すると、** 時間の複雑さは__O（nLogn）になります。

これは、配列を常に2つに分割してからマージするため、最悪、平均、最良の場合に当てはまります。

アルゴリズムのスペースの複雑さは、再帰呼び出しごとに一時配列を作成するため、

O（n）

です。

5.まとめ

このクイックチュートリアルでは、マージソートアルゴリズムの動作と、それをJavaで実装する方法について説明しました。

ワーキングコード全体はhttps://github.com/eugenp/tutorials/tree/master/algorithms-sorting[GitHubで利用可能]です。