Implementation in java for Merge Sort.

Hello Friends,

Today I am here with Implementation of Merge Sort in Java. Its a divide and conquer algorithm as it breaks down the input array and then merge them and finally we have a full sorted merged array.


Before discussing merge sort I would like to induce an idea of how  Recursion can be used for  Stack. (actually stack is used to hold the method state in method calls). For this go through the code below

package com.algorithm.sorting;

public class MergeSort {

    public static void mergeSort(int[] array) {
        divide(array);
    }

    public static void divide(int[] array) {
        int n = array.length;
        if (n < 2) {
            return;
        }
        int mid = n / 2;
        int[] left = new int[mid];
        for (int i = 0; i < mid; i++) {
            left[i] = array[i];
        }
        int[] right = new int[n - mid];

        // this loop is interesting and prone for a mistake, so be careful with
        // this loop.
        // it goes from mid to end but in the right array, input needs to be
        // filled from 0 on wards,
        // hence mid is subtracted from i
        for (int i = mid; i < n; i++) {
            right[i - mid] = array[i];
        }

        divide(left);
        divide(right);
        conquer(left, right, array);
    }

    public static void conquer(int[] left, int[] right, int[] array) {
        int i = 0, j = 0, k = 0;
        int nl = left.length;
        int nr = right.length;
        while (i < nl && j < nr) {

            // <= is needed to keep merge sort a stable sort
            if (left[i] <= right[j]) {
                array[k++] = left[i++];
            } else {
                array[k++] = right[j++];
            }
        }
        while (i < nl) {
            array[k++] = left[i++];
        }
        while (j < nr) {
            array[k++] = right[j++];
        }
    }
}