Posted at

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