Merge sort Implementation

 Merge sort : In merge sort we will divide the array from middle recursively  until we have only one element in sub-array. After that we will merge sub-array in ascending order.

    Time complexity for merge sort will be O(nlogn) as we are splitting the array from middle so each time it's getting half so for that  it will be log(n) and while merging we are traversing the whole array so for that it will be O(n).
     So after combining both  time complexity will be O(n)+O(logn)= O(nlogn)
     space complexity will be O(n) as we need a extra same size array to hold the unsorted array.

class MergeSort {

    public static void sort(int[] array) {
        int[] aux = new int[array.length];
        sort(array, aux, 0, array.length - 1);
    }

    private static void sort(int[] array, int[] aux, int lo, int hi) {
        if (hi <= lo) return;
        int mid = (lo + hi) / 2;
        sort(array, aux, lo, mid);
        sort(array, aux, mid + 1, hi);
        merge(array, aux, lo, mid, hi); // [lo, mid] [mid + 1, hi] => [lo, hi]
    }

    private static void merge(int[] array, int[] aux, int lo, int mid, int hi) {
        for (int i = lo; i <= hi; i++) {
            aux[i] = array[i];
        }

        int i = lo;
        int j = mid + 1;
        for (int k = lo; k <= hi; k++) {
            if (i > mid) {
                array[k] = aux[j];
                j++;
            } else if (j > hi) {
                array[k] = aux[i];
                i++;
            } else if (aux[j] < aux[i]) {
                array[k] = aux[j];
                j++;
            } else {
                array[k] = aux[i];
                i++;
            }
        }
    }

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

    public static void main(String[] args) {
        int[] array = {111, 80, 14, 21, 19, 31, 19, 121, 10, 190, 80, 6, 7};
        sort(array);
        print(array);
    }
}

Please have a look to the  source code of all sorting method from below link

1. BUBBLE SORT PROGRAM
2. SELECTION SORT PROGRAM
3. INSERTION SORT PROGRAM
4. MERGE SORT PROGRAM
5. QUICK SORT PROGRAM