Merge Sort is a divide and conquer algorithm based on the idea of breaking a list down into several sublists until each sublist contains only a single item. Afterwards, we will merge these sublists in such a manner that the resulting list will be sorted.

Essential Idea

1. Divide the list into sub-lists, each containing a single element.
2. Merge adjacent pairs of two "singleton" (containing only one element) lists to form a list of 2 elements.
3. Repeat the above steps, until we get a fully sorted list.

Let's consider an example to understand this approach better.

We have an array containing eight elements and two pointers directed at the first and last element.

Dividing the array

One can understand from the images below that at each step, the array of size M is divided into two sublists, of size M/2, until no further division is possible.

We divide the array using the function merge_sort(array, startIndex, lastIndex). As shown in the images above, merge_sort recursively divided the array into halves until we reach the base case where each subarray contains only single element.

Merging the sub-arrays

After dividing the array, we will call the merge function that picks up the sorted sub-arrays and combines them to gradually sort the array. This function will also merge the sub-arrays recursively in such a way that a fully sorted array can be obtained.

The below images demonstrates the merging of an array in action.