MergeShorts.java

/**
 * Created by : fb.com/realprakashpandey on 24/8/16.
 * About Program : Java implimentation of merge sort.
 /

public class MergeSorts
{
    /* @ int [] array : sample input for sorting, you can provide any list of number here */
    static int[] array= {3, 35 ,4 ,85};

    /**
     * implement divide and conquer
     * divide the list until list contain only one element
     * @param B : array to divide
     * @return
     */
    static int[] Sort(int[]B) {

        if (B.length <= 1)
        {
            return B;
        }
        int listLength = B.length;
        int midpoint = listLength/2;
        int[] left = new int[midpoint];
        int[] right = new int[listLength - midpoint];
        int[] result = new int[listLength];

        for (int i=0; i<midpoint; i++)
        {
            left[i] = B[i];
        }

        int x=0; // initialize right from index : 0
        for (int j=midpoint; j<listLength; j++)
        {
            if (x < right.length)
            {
                right[x++] = B[j];
            }
        }

        left = Sort(left);
        right = Sort(right);
        result = merge(left, right);
        return result;
    }

    /**
     * merge two arrays into one and return sorted one
     * @param a : sorted array 'a'.
     * @param b : sorted array 'b'.
     * @return  : combination of array 'a+b' in sorted order.
     */
    public static int[] merge(int a[], int b[]) {
        int indexA, indexB, index;
        indexA = 0;
        indexB = 0;
        index = 0;
        int sizeA, sizeB, size;
        sizeA = a.length;
        sizeB = b.length;
        size = sizeA + sizeB;
        int[] result = new int[size];
        while (indexA < sizeA || indexB < sizeB) {
            /**
             * if both array a,b have element
             */
            if (indexA<sizeA && indexB<sizeB) {
                /**
                 * check smaller one and add to list result
                 */
                if (a[indexA] <= b[indexB]) {
                    result[index++] = a[indexA++];
                }
                else {
                    result[index++] = b[indexB++];
                }
            }
            /**
             * only element of array 'a' is remaining
             * add it to list direct
             */
            else if (indexA < sizeA) {
                result[index++] = a[indexA++];
            }
            /**
             * only element of array 'b' is remaining.
             */
            else {
                result[index++] = b[indexB++];
            }
        }
        return result;
    }

    /**
     * print sorted list
     * @param sortedList list already sorted
     */
    public static void printList(int[] sortedList , String msg) {
        System.out.print(msg);
        for (int i=0; i<sortedList.length; i++) {
            System.out.print(sortedList[i] + " ");
        }
        System.out.println();
    }

    /**
     * main function.
     * @param args : no use of main arguments.
     */
    public static void main(String[] args) {

        printList(array, "Before Sorting : ");
        printList(Sort(array), "After Sorting : ");
    }
}