Mergesort Java

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

 

Scroll to Top