【Java入門】マージソートの実装方法をサンプルコードで解説

マージソートは、配列を半分に分割し、それぞれを整列させてから統合（マージ）することで全体を並べ替える、分割統治法に基づく代表的なソートアルゴリズムです。平均・最悪ともに計算量が O(n log n) であり、安定したソートとしても知られています。

以下は、Javaでマージソートを実装したサンプルプログラムです。

サンプルプログラム

import java.util.Arrays;
public class Demo{
    public static void merge_sort(int[] my_arr){
        if(my_arr == null){
            return;
        }
        if(my_arr.length > 1){
            int mid = my_arr.length / 2;
            int[] left = new int[mid];
            for(int i = 0; i < mid; i++){
                left[i] = my_arr[i];
            }
            int[] right = new int[my_arr.length - mid];
            for(int i = mid; i < my_arr.length; i++){
                right[i - mid] = my_arr[i];
            }
            merge_sort(left);
            merge_sort(right);
            int i = 0;
            int j = 0;
            int k = 0;
            while(i < left.length && j < right.length){
                if(left[i] < right[j]){
                    my_arr[k] = left[i];
                    i++;
                } else {
                    my_arr[k] = right[j];
                    j++;
                }
                k++;
            }
            while(i < left.length){
                my_arr[k] = left[i];
                i++;
                k++;
            }
            while(j < right.length){
                my_arr[k] = right[j];
                j++;
                k++;
            }
        }
    }
    public static void main(String[] args){
        int my_arr[] = {56, 78, 91, 21, 34, 0, 11};
        int i=0;
        merge_sort(my_arr);
        System.out.println("The array after sorting is ");
        for(i=0; i
実行結果
The array after sorting is
0 11 21 34 56 78 91
プログラムの解説
merge_sortメソッドの処理の流れ
Demoクラスには「merge_sort」メソッドが定義されています。まず引数として渡された配列が null かどうかを判定し、null の場合は何もせずに処理を終了します。
配列の要素数が1より大きい場合は、中央位置「mid」を算出し、配列を前半と後半の2つに分割します。前半の要素は新しい配列「left」へ、後半の要素は別の配列「right」へそれぞれコピーされます。
分割された各配列に対しては再帰的に merge_sort を呼び出すことで個別に整列を行い、その後、left と right の先頭から順に値を比較しながら小さい方から元の配列へ書き戻していきます。どちらか一方の要素を使い切ったら、残りの要素をそのまま末尾に連結し、完全に整列された配列が完成します。
mainメソッドの処理
mainメソッドでは、整数型の配列 {56, 78, 91, 21, 34, 0, 11} を定義し、この配列を引数として merge_sort メソッドを呼び出しています。ソート後の配列の内容がコンソールに出力され、昇順に並べ替えられた結果を確認できます。