Mergesort Java
Typer | Posted on | |
import java.util.Arrays;
public class MergesortElegant {
public static void main(String[] args) {
int[] data = { 13, 7, 1, 3, 2, 5, 4, 6, 8, 10, 12, 11, 9 };
// 1. Initial State
System.out.println("-------------------- Initial State --------------------");
System.out.println(Arrays.toString(data) + "\n");
int n = data.length;
if (n > 1) {
int mid = n / 2;
int[] B = Arrays.copyOfRange(data, 0, mid);
int[] C = Arrays.copyOfRange(data, mid, n);
// 2. Divided State
System.out.println("-------------------- Divided State --------------------");
System.out.println("Left Side (B): " + Arrays.toString(B));
System.out.println("Right Side (C): " + Arrays.toString(C) + "\n");
// Silent internal sort
actualSort(B);
actualSort(C);
// 3. Merged State
int[] result = new int[n];
merge(B, C, result);
System.out.println("-------------------- Merged State --------------------");
System.out.println(Arrays.toString(result));
}
}
private static void actualSort(int[] A) {
if (A.length <= 1)
return;
int mid = A.length / 2;
int[] B = Arrays.copyOfRange(A, 0, mid);
int[] C = Arrays.copyOfRange(A, mid, A.length);
actualSort(B);
actualSort(C);
merge(B, C, A);
}
private static void merge(int[] B, int[] C, int[] A) {
int i = 0, j = 0, k = 0;
while (i < B.length && j < C.length) {
if (B[i] <= C[j])
A[k++] = B[i++];
else
A[k++] = C[j++];
}
if (i == B.length)
System.arraycopy(C, j, A, k, C.length - j);
else
System.arraycopy(B, i, A, k, B.length - i);
}
}