FOR FREE MATERIALS

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:

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)
		}
	}