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));
    }
}