Merge Sort

Merge sort is one of the most efficient sorting algorithms. It works on the principle of Divide and Conquer. Merge sort repeatedly breaks down a list into several sublists until each sublist consists of a single element and merging those sublists in a manner that results into a sorted list.

    public static void process(int[] input) {
        if (input == null || input.length == 0) return;

        mergeSort(input, 0, input.length - 1);
    }

    public static void mergeSort(int[] input, int left, int right) {
        if (left >= right) {
            return;
        }

        int mid = left + (right - left) / 2;

        mergeSort(input, left, mid);
        mergeSort(input, mid + 1, right);

        merge(input, left, mid, right);
    }

    public static void merge(int[] arr, int left, int mid, int right) {
        int[] A = new int[mid - left + 1];
        int[] B = new int[right - mid];

        // copy elements
        for (int i = 0; i < A.length; ++i) {
            A[i] = arr[left + i];
        }

        for (int i = 0; i < B.length; ++i) {
            B[i] = arr[mid + 1 + i];
        }

        // sort
        int p1 = 0, p2 = 0, i = left;
        while (p1 < A.length && p2 < B.length) {
            if (A[p1] < B[p2]) {
                arr[i++] = A[p1++];
            } else {
                arr[i++] = B[p2++];
            }
        }

        // process the remaining
        while (p1 != A.length) {
            arr[i++] = A[p1++];
        }

        while (p2 != B.length) {
            arr[i++] = B[p2++];
        }
    }

Three are two steps:

Top-down Merge Sort Implementation:

The top-down merge sort approach is the methodology which uses recursion mechanism. It starts at the Top and proceeds downwards, with each recursive turn asking the same question such as “What is required to be done to sort the array?” and having the answer as, “split the array into two, make a recursive call, and merge the results.”, until one gets to the bottom of the array-tree.

Bottom-Up Merge Sort Implementation:

The Bottom-Up merge sort approach uses iterative methodology. It starts with the “single-element” array, and combines two adjacent elements and also sorting the two at the same time. The combined-sorted arrays are again combined and sorted with each other until one single unit of sorted array is achieved.

Space complexity: O(nlogn)

Time complexity: O(n)