/Merge Sort

Merge Sort

Merge Sort

public class Mergesort {

    public static void main(String args[]) {
        int a[] = {4, 2, 3, 1, 6, 5, 0};
        mergesort(a, 0, a.length - 1);
        printArray(a);
    }

    private static void printArray(int a[]) {
        for (int i = 0; i < a.length; i++) {
            if (a.length - 1 == i) {
                System.out.println(a[i]);
                break;
            }
            System.out.print(a[i] + " ");
        }
    }

    private static void mergesort(int a[], int p, int q) {
        if (p < q) {
            int middle = ((p + q) / 2);
            mergesort(a, p, middle);
            mergesort(a, middle + 1, q);
            merging(a, p, middle, q);
        }
    }

    private static void merging(int a[], int p, int k, int q) {
        int b[] = new int[a.length];
        for (int i = 0; i < a.length; i++) {
            b[i] = a[i];
        }

        int i = p;
        int j = k + 1;
        int x = p;
        while (i <= k && j <= q) {
            if (b[i] < b[j]) {
                a[x] = b[i];
                i += 1;
                x += 1;
            } else {
                a[x] = b[j];
                j += 1;
                x += 1;
            }
        }

        while (i <= k) {
            a[x] = b[i];
            i += 1;
            x += 1;
        }

        while (j <= q) {
            a[x] = b[j];
            j += 1;
            x += 1;
        }
    }
}