Merge Sort-Know More

Merge Sort is one of the most efficient and quick sorting algorithms. Merge Sort is based on the principle of Divide and Conquer, similar to the QuickSort algorithm. In this algorithm, the given array of elements is split into two halves repeatedly until the halves only have two elements. Then those fragments are sorted, then all of them are merged to produce the final array. This algorithm is one of the fastest and is the best algorithm to be used for longer lists or arrays. let us know more about that the Merge Sort-Know More.

Divide and Conquer Strategy

Merge sort uses the divide and conquer technique. In the divide and conquer technique, you split the problem into smaller parts, they are solved and then the solution is merged to solve the main problem.

For example, let’s say we have an array A. Then we split or divide the array into two halves at the index i, i.e., A[: i] and A[i:]. Then the problems are conquered, i.e. in this case sorted. Then they are combined to produce the final solution, A.

Using this strategy the algorithm reduces the complexity significantly.

MergeSort Algorithm

In the MergeSort function, the array is split into halves until the size of one fragment becomes 1 i.e. l==r. Then all of the fragments are sorted and then the merge function combines all of the sorted arrays and makes the final result.

The algorithm can be written as follows.

MergeSort(list, l, r):

If l > r:

return;  

m = (l+r)/2;  //Find the middle point to divide the list

MergeSort(list,l,m);  //Call the function on the left half

MergeSort(list,m+1,r);  //Call the function on the right half

Merge(A,l,m,r);  //Merge the two halves

Here’s an example

We have an array = {38, 27, 43, 3, 9, 82, 10}

Then split the array = {38, 27, 43, 3}, {9, 82, 10}

And again = {38,27}, {43,3}, {9, 82}, {10}

As we cannot split anymore, we start sorting = {27,38}, {3,43}, {9,82}, {10}

Then we start merging = {3, 27, 38 ,43}, {9, 10, 82}

Then we merge again = {3, 9, 10, 27, 38, 43, 82}

Merge Sort Advantages and Disadvantages

Merge sort is one of the quickest sorting algorithms. It has a worst-case time complexity of O(nlogn). The algorithm is best for large lists because it doesn’t traverse the list multiple times like insertion and bubble sort and it’s also pretty stable.

Merge sort is used in different applications like:-

• Inversion count problem – This problem denotes how far the array is from being sorted.
• External Sorting – A class of sorting algorithms that can manage large amounts of data.

But compared to other algorithms, it is slow for smaller lists compared to other sorting lists. It requires additional space O(n) memory for a temporary array.

How to write the code?

We’ll use Python in this example for quick prototyping, but it’ll be easy to understand and be implemented in other languages. If you follow the algorithm, you can also implement it in other languages like C or Java. So let’s begin.

First, we will take an array, the first position, and the last position of the first subarray and the second subarray and give them to the merge function.

We are supposed to merge two arrays A[i…k] and A[k+1…j]. So the inputs are A, i, k, j.

[Note: in Python. We don’t need to give the i,j,k arguments as we can calculate it.]

The function works as follows:

1. Create copies of subarrays A[i…k] and A[k+1…j]
2. Create three iterators n1, n2 and l
   1. n1 is an index of the left array 
   2. n2 is an index of the right array
   3. l is the index of A[i…j]
3. Until the iterators reach the end of their respective arrays, pick the larger element from n1 or n2 and put them at A[i…j]
4. When either array is empty, then put the rest into the main array.

So let’s implement the above-  algorithm in Python. In practice, it’ll look like this.

Python

def MergeSort(A):

if len(A) > 1:

#r is the midpoint of the list where it’ll be divided

m = len(A)//2

l = A[:m]

r = A[m:]

MergeSort(l)

MergeSort(r)

i = 0

j = 0

k = 0

#We’ll reach the end of either the left array or the right and until then

#the larger element will be picked from them and placed in the array

while i < len(l) and j < len(r):

if l[i] < r[j]:

A[k] = l[i]

i += 1

else:

A[k] = r[j]

j += 1

k += 1

 #Now that we have sorted the elements. The rest will be put

#in the array

while i < len(l):

A[k] = l[i]
i += 1

k += 1

while j < len(r):

A[k] = r[j]

j += 1

k += 1

#main program

arr_merge = [5,1,49,2,330,12]

MergeSort(arr_merge)

print(“The sorted array is:”, arr_merge)

Conclusion

Merge Sort is one of the most efficient sorting algorithms and one of the most important algorithms to study in a Data Science course.  For any other queries like how to implement in a different language like C or Java, contact us.

FAQ

Is there any alternative to Merge Sort?

Yes, some of them include Quick Sort and Bucket sort.

What kind of strategy does Merge Sort use?

Merge Sort uses Divide and Conquer strategy to sort a list

What is the time complexity of Merge Sort?

The time complexity of Merge Sort is  O(nlogn). 

What is the space complexity of Merge Sort?

As Merge Sort requires a temporary array, the space complexity is O(n).

What are the ways I can code Merge Sort?

You can iteratively and recursively program Merge Sort.

Is Merge Sort good for small lists?

Unlike long lists, small lists won’t benefit from merge sorts as the algorithm traverses the list multiple times and is slower than other algorithms.

Is Merge Sort stable?

Yes, the Merge sort algorithm is very stable.