復習
import java.util.Arrays;
import java.util.Random;
public class MergeSort {
public static void mergesort(int[] arr) {
mergesort(arr, 0, arr.length);
}
static void mergesort(int[] arr, int i, int j) {
// arrのうち、i <= x < jの区間をソートする
if (j - i <= 1) {
// ソート済み
return;
}
int mid = i + (j - i) / 2;
mergesort(arr, i, mid);
mergesort(arr, mid, j);
merge(arr, i, mid, j);
}
static void merge(int[] arr, int i, int mid, int j) {
int size = j - i;
int[] work = new int[size];
System.arraycopy(arr, i, work, 0, size);
int k = i;
int p = 0;
int q = mid - i;
while (p < (mid - i) && q < size) {
if (work[p] <= work[q]) {
arr[k++] = work[p++];
} else {
arr[k++] = work[q++];
}
}
while (p < (mid - i)) {
arr[k++] = work[p++];
}
while (q < size) {
arr[k++] = work[q++];
}
}
public static void main(String[] args) {
int[] arr = new int[100];
Random r = new Random(System.nanoTime());
for (int i = 0; i < arr.length; i++) {
arr[i] = r.nextInt(100);
}
System.out.println(Arrays.toString(arr));
mergesort(arr);
System.out.println(Arrays.toString(arr));
}
}