マージソートの実装

基本情報とJava学習目的

マージソートとは

• 配列を前半と後半に再帰的に分割
• ↑を最終的に要素数が1になるまで繰り返す
• 分割した配列を比較し、小さい（大きい）順にマージ（併合）する
• クイックソート並みに計算量が少ないが、必要なメモリ量（配列）がクイックソートより多いのでクイックソートよりは遅い

実装したコード

MergeSort

import java.util.*;
public class MergeSort {
    public static void main(String[] args) {
        int[] ary = {9,13,11,5,1,8,14,15,4,12,3,16,2,7,10,6};
        int left = 0;
        int right = ary.length;
        MergeSort2.Split (ary, left, right);
        System.out.println(Arrays.toString(ary));
    }
}

MergeSort2

public class MergeSort2 {
    public static void Split(int[] ary, int left, int right) {
        // 分割アルゴリズム
        if (right - left <= 1) {
            return;
        }
        int mid = left + (right - left) / 2;
        Split(ary, left, mid);// 前半部分を再帰的に分割
        Split(ary, mid, right);// 後半部分を分割
        Merge(ary, left, mid, right);

    }

    public static void Merge(int[] ary, int left, int mid, int right) {
        //併合アルゴリズム
        int amtleft = mid - left;
        int amtright = right - mid;
        int[] aryleft = new int[amtleft];
        int[] aryright = new int[amtright];

        for (int i = 0; i < amtleft; i++) {
            aryleft[i] = ary[left + i]; //配列の前半部分をローカルの配列に転記
        }
        //aryleft[i + 1] = 10000; //上限値
        for (int j = 0; j < amtright; j++) {
            aryright[j] = ary[mid + j];
        }
        //aryright[j + 1] = 10000;
        int i = 0, j = 0, k = left;
        while (i < amtleft && j < amtright) {
            if (aryleft[i] <= aryright[j]) {
                ary[k++] = aryleft[i++];
            } else {
                ary[k++] = aryright[j++];
            }
        }
        while (i < amtleft) {
            ary[k++] = aryleft[i++];
        }
        while (j < amtright) {
            ary[k++] = aryright[j++];
        }
    }
}

参考文献

満を持して登場、しめじソートが綺麗【マージソート】
【Java】マージソート