Merge Sort

Merge sort is a kind of sorting technique is based on divide and conquer technique.. This algorithm is based on splitting a list, into 2 comparable sized lists i.e.

left and right and then sorting each list and then merging the two sorted lists back together as one.

In merge sort the unsorted list is divided into N sublists, each having one element, because a list consisting of one element is always sorted. Then, it repeatedly merges these sublists, to produce new sorted sublists, and in the end, only one sorted list is produced.

Merge Sort is quite fast, and has a time complexity of O(n log n). It is also a stable sort, which means the "equal" elements are ordered in the same order in the sorted list.

Before jumping on to, how merge sort works and it's implementation, first lets understand what is the rule of Divide and Conquer?

Divide and Conquer

If we can break a single big problem into smaller sub-problems, solve the smaller sub-problems and combine their solutions to find the solution for the original big problem, it becomes easier to solve the whole problem.

Let's take an example of Divide and Rule.

When Britishers came to India, they saw a country with different religions living in harmony, hard working but naive citizens, unity in diversity, and found it difficult to establish their empire. So, they adopted the policy of Divide and Rule. Where the population of India was collectively a one big problem for them, they divided the problem into smaller problems, by instigating rivalries between local kings, making them stand against each other, and this worked very well for them.

Well that was history, and a socio-political policy (Divide and Rule), but the idea here is, if we can somehow divide a problem into smaller sub-problems, it becomes easier to eventually solve the whole problem.

In Merge Sort, the given unsorted array with n elements, is divided into n subarrays, each having one element, because a single element is always sorted in itself. Then, it repeatedly merges these subarrays, to produce new sorted subarrays, and in the end, one complete sorted array is produced.

The concept of Divide and Conquer involves three steps:

1.    Divide the problem into multiple small problems.

2.    Conquer the subproblems by solving them. The idea is to break down the problem into atomic subproblems, where they are actually solved.

3.    Combine the solutions of the subproblems to find the solution of the actual problem.

Merge sort can be done in two types both having similar logic and way of implementation. These are:

• Top down implementation :Top-down merge sort algorithm that recursively splits the list (called runs in this example) into sublists until sublist size is 1, then merges those sublists to produce a sorted list. The copy back step is avoided with alternating the direction of the merge with each level of recursion.
• Bottom up implementation: Bottom-up merge sort algorithm which treats the list as an array of n sublists (called runs in this example) of size 1, and iteratively merges sub-lists back and forth between two buffers

How Merge Sort works?

As we have already discussed that merge sort utilizes divide-and-conquer rule to break the problem into sub-problems, the problem in this case being, sorting a given array.

In merge sort, we break the given array midway, for example if the original array had 6 elements, then merge sort will break it down into two subarrays with 3 elements each.

But breaking the original array into 2 smaller subarrays is not helping us in sorting the array.

So we will break these subarrays into even smaller subarrays, until we have multiple subarrays with single element in them. Now, the idea here is that an array with a single element is already sorted, so once we break the original array into subarrays which has only a single element, we have successfully broken down our problem into base problems.

And then we have to merge all these sorted subarrays, step by step to form one single sorted array.

Let's consider an array with values {14, 7, 3, 12, 9, 11, 6, 12}

Below, we have a pictorial representation of how merge sort will sort the given array.

Merge Sort Algorithm:

In merge sort we follow the following steps:

1.    We take a variable p and store the starting index of our array in this. And we take another variable r and store the last index of array in it.

2.    Then we find the middle of the array using the formula (p + r)/2 and mark the middle index as q, and break the array into two subarrays, from p to q and from q + 1 to r index.

3.    Then we divide these 2 subarrays again, just like we divided our main array and this continues.

4.    Once we have divided the main array into subarrays with single elements, then we start merging the subarrays.

MergeSort(arr[], l,  r)
If r > l
     1. Find the middle point to divide the array into two halves:  
             middle m = (l+r)/2
     2. Call mergeSort for first half:   
             Call mergeSort(arr, l, m)
     3. Call mergeSort for second half:
             Call mergeSort(arr, m+1, r)
     4. Merge the two halves sorted in step 2 and 3:
             Call merge(arr, l, m, r)

 ⇒Merge Sort in C Code: http://bit.ly/2CRh5Xn

Merge Code  Complexity:

• Worst Case Time Complexity : O(n log n)
• Best Case Time Complexity : O(n log n)
• Average Time Complexity : O(n log n)
• Space Complexity : O(n)

Time complexity of Merge Sort is O(n Log n) in all 3 cases (worst, average and best) as merge sort always divides the array in two halves and take linear time to merge two halves.

It requires equal amount of additional space as the unsorted list. Hence its not at all recommended for searching large unsorted lists.

It is the best Sorting technique used for sorting Linked Lists.