MergeSort

今回は、MergeSort（マージソート）のプログラムを書いてみました。

マージソートは、数列を2つに分けて、
それぞれを再帰的にソートしてからくっつける分割統治法です。
計算量はO(nlogn)です。

再帰って、便利ですね！

MergeSort.java

import java.util.*;
public class MergeSort {
    public static boolean debug = false;
    private static void mergeSort(int[] a,int low,int high){
    if(low >= high) return;
    int mid = (low + high) / 2;
    mergeSort(a,low,mid);
    mergeSort(a,mid+1,high);
    int[] b = new int[mid-low+1];
    for(int i = 0; i < b.length; i++) b[i] = a[low+i];
    int i = 0;
    int j = mid + 1;
    for(int idx = low; idx <= high; idx++) {
        if(i >= b.length) a[idx] = a[j++];
        else if(j > high) a[idx] = b[i++];
        else if(b[i] < a[j]) a[idx] = b[i++];
        else a[idx] = a[j++];
    }
    if(debug) System.out.println("low="+low+", high="+high+", mid="+mid+": "+toString(a));

    }
    public static void sort(int[] a){mergeSort(a,0,a.length-1);}
    public static String toString(int[] a) {
    StringBuffer sb = new StringBuffer();
    for(int i = 0; i < a.length; i++) sb.append(a[i]+" ");
    return sb.toString();
    }
    public static void main(String[] args) {
    if(args.length > 0 && args[0].equals("-d")) debug = true;
    Scanner sc = new Scanner(System.in);
    System.out.print("データの個数を入力してください ");
    int n = sc.nextInt();
    int[] a = new int[n];
    for (int i = 0; i < n; i++) a[i] = sc.nextInt();
    sort(a);
    System.out.println(toString(a));
    }
}