CREATE OWN LIBRARY

Merge Sort using recursion

Back to Programming

Description

Merge sort is a comparison-based sorting algorithm that follows a divide and conquers paradigm to sort the elements in ascending or descending order. Though it is a comparison based sorting technique, it is different from bubble or selection sort. The logic may be little complicated than those sorting technique but this sorting technique are better in terms of time complexity and the number of comparisons is also less than them. The space complexity of this algorithm is more than some other sorting techniques as it needs 2n space to sort n no. of data.

 

The procedure with an example:

Suppose there is an array of 7 elements as following and it has to be sorted in ascending order:

 

 

 

Step 1: According to the logic of merge sort the array will be divided into two halves then the sub-arrays will again be divided into two halves and so on until it reaches all single element arrays. So for the above example, the array will first be divided into two halves as follows:

 

Half 1:   

 

 

Half 2:

 

 

Step 2:

In the next step, the 1st half will again be divided into two arrays, the first array will contain the elements 45 and 36, the second array will contain the elements 12 and 75. The 2nd half will also be divided into two arrays in which the first array will contain 2 and 19 and the 2nd array will have only one element i.e. 25.

 

After this step, we will get the arrays as:

 

 

 

Step 3:

In this step we will get all single element arrays as these above pairs of elements will again be divided into halves and for n number of elements into n number of arrays will be formed. As here the number of elements is 7 so we will get 7 single element arrays as:

 

 

This is the division part of the divide and conquers paradigm now the elements will be conquered again by reversing the division rule and at the time of conquering the sorting will be performed and the sorted elements will be stored into another array.

 

Step 4:

First, the first two single-element arrays will be compared and will be conquered in sorted order. For this example, 45 and 36 will be compared. As 45 is greater than 36, 36 will be inserted into the other array. Similarly, 12 and 75 will be compared and will be inserted according to their sorted order. Then 2 and 19 will be compared and inserted in sorted order. 25 will be inserted at the last. So after conquering for the first time the arrays will be:

 

 

Step 5:

Now 36 will be compared to 12, as 12 < 36 then 12 will be inserted into the other array where the sorted array will be stored. After that 36 will again be compared with 75 and as 36 < 75 so 36 will be inserted into the sorted array. Lastly, 45 and 75 will be compared and will be inserted into the sorted array according to their sorted order. After this the conquered array will be:

 

 

Similarly, the next two pairs of the array will be compared and the conquered array will be: 

 

 

Step 6:

At the last step of conquering, here we compare elements of two lists one by one. 12 will be compared to 2. As 2 is less than 12, 2 will be inserted first in the sorted array. After that 12 is again compared to 19, in this case as 12 is lesser than 19, 12 is inserted into the sorted array. Now 19 and 36 are compared and 19 have been inserted into the sorted array, then 25 and 36 are compared and 25 are inserted into the sorted array. After this, there is no unsorted element in the 2nd half of the array. So in this situation, all the rest elements of the first half will be inserted into the sorted array without any comparisons as already the elements of that half are sorted.

 

Lastly, we will get the final sorted array as:

 

 

Divide and conquer procedure by tree:

 

 

Algorithm

MERGE (A, p, q, r)
	{	n_1=q-p+1
		n_2=r-q
		Let L[1 ……. n_1 + 1] and R[1 to n_2 + 1]  be new arrays
			for(i = 1 to n_1)
			{
				L[i] = A[p + i – 1]
			}
for(j = 1 to n_2)
			{
				R[j] = A[q + j]
			}
			L^' [n_1+1]=∞
			R[n_2+1]=∞
			i = 1, j = 1
			for(k = p to r)
				if(L[i] <= R[j])
					A[k] = L[i]
					i = i + 1
				else  A[k] = R[j]
					j = j + 1
	}

 

Merge_sort(A, p, r)
	{        if(p < r)
		{            q = ⌊(p + r)/ 2⌋   // mid point
			Merge_sort(A, p, q)
			Merge_sort (A, q + 1, r)
			Merge (A, p, q, r)
		}
	}

Code

CHARACTERISTICS of Merge Sort:

1. It is based on the divide and conquers paradigm.

 

2. It is a comparison-based sorting technique.

 

3. Merge sort is faster than the insertion sort technique.

 

4. It is a comparison-based sorting algorithm.

 

5. It is a stable sorting technique.

 

TIME COMPLEXITY:

Merge_sort(A, p, r) _______________ T(n) (Let)

            {           if(p < r)

                        {           q = ⌊(p + r)/ 2⌋     // mid point

                                    Merge_sort(A, p, q) _____________ T(n/2)

                                    Merge_sort (A, q + 1, r) _________ T(n/2)

                                    Merge (A, p, q, r) _________________ O(n)

                        }

            }

 

So, 

 

[For details please see masters theorem and substitution method to calculate time complexity of a recursive algorithm]

 

Here we solve it by master theorem: 

 

Master Theorem: 

https://mycareerwise.com/storage/editor/images/Master%20theorem.png 

 

 

And in this case one condition has satisfied that is: 

 

And also p > -1, then    [for details please follow the master theorem]

 

 

If we put the value of a, b, and p  we will get:

 

 

SPACE COMPLEXITY:

In merge sort, it always divides the array from the middle position, so, total division tree of the sorting process will be always balanced.  

 

In the case of a balanced tree, we know the number of stacks required to solve this recursion is equal to height of the tree. And height of the balanced tree for n number is  log n.  

 

 

And space complexity to merge two arrays into single array of size n.

 

 

ADVANTAGES of merge sort:

1. It sorts a large array very quickly.

 

2. Time complexity is lesser than a bubble or selection sort.

 

3. It is a stable sorting technique.

 

4. It has a consistent running time.

 

5. It can be executed using a parallel computing technique.

 

DISADVANTAGES of merge sort:

1. It is not an in-place algorithm i.e. it requires extra memory space for sorting.

 

2. It is slower than the other sorting techniques for smaller data.

 

3. It performs the whole process if the array is sorted just like other sorting techniques.