Question 80 : Can you write algorithm for merge sort and also do you know complexity of merge sort?

Merge sort is divide and conquer sorting algorithm. It is efficient, comparison based sorting algorithm.

It works on below principle:

• Divide list into sublist of about half size in each iteration until each sublist has only one element.
• Merge each sublist repeatedly to create sorted list. It will run until we have only 1 sorted list. This will be the sorted list.

The below diagram will make it clearer:

Merge sort implementation

I have printed intermediate steps to understand the algorithm better

class Solution {

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

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

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

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

    private void merge(int[] arr, int left, int mid, int right) {

        int n1 = mid - left + 1;
        int n2 = right - mid;

        int[] L = new int[n1];
        int[] R = new int[n2];

        for (int i = 0; i < n1; i++)
            L[i] = arr[left + i];

        for (int j = 0; j < n2; j++)
            R[j] = arr[mid + 1 + j];

        int i = 0, j = 0, k = left;

        while (i < n1 && j < n2) {
            if (L[i] <= R[j])
                arr[k++] = L[i++];
            else
                arr[k++] = R[j++];
        }

        while (i < n1)
            arr[k++] = L[i++];

        while (j < n2)
            arr[k++] = R[j++];
    }
}

When you run above program , you will get following output:

Array before sorting:
100 20 15 30 5 75 40
—————————–
Before Merging: 100 20
After merging: 20 100

Before Merging: 15 30

After merging: 15 30

Before Merging: 20 100 15 30
After merging: 15 20 30 100

Before Merging: 5 75
After merging: 5 75

Before Merging: 5 75 40
After merging: 5 40 75

Before Merging: 15 20 30 100 5 40 75
After merging: 5 15 20 30 40 75 100

—————————–
Array After sorting:
5 15 20 30 40 75 100

Time Complexity:

Best case: O(nlogn)
Average case: O(nlogn)
Worst case: O(nlogn)