A Simplified Explanation of Merge Sort

Divide and Conquer Approach

What is Merge Sort and how is it associated with Algorithms?

Merge Sort is a sorting algorithm, which is commonly used in computer science. Merge Sort is a divide and conquer algorithm. It works by recursively breaking down a problem into two or more sub-problems of the same or related type until these become simple enough to be solved directly.

The solutions to the sub-problems are then combined to give a solution to the original problem. So Merge Sort first divides the array into equal halves and then combines them in a sorted manner.

Merge sort is similar to the quick sort algorithm as it uses the divide and conquer approach to sort the elements. It is one of the most popular and efficient sorting algorithms. It divides the given list into two equal halves, calls itself for the two halves and then merges the two sorted halves. We have to define the merge() function to perform the merging.

Merge Sort Algorithms: How it works:

1. If it is only one element in the list it is already sorted, return.
2. Divide the list recursively into two halves until it can no more be divided.
3. Merge the smaller lists into a new list in sorted order.

Important Characteristics of Merge Sort:

• Merge Sort is a stable sort which means that the same element in an array maintain their original positions with respect to each other.
• The overall time complexity of the Merge sort is O(nLogn). It is more efficient than it is in the worst case also the runtime is O(nlogn)
• The space complexity of the Merge sort is O(n). This means that this algorithm takes a lot of space and may slow down operations for the last data sets.

Critical ideas to think in merge sort!

• For the smaller input, It is slower in comparison to other sorting algorithms. Even it goes through the complete process if the array is already or almost sorted.
• Merge sort is the best choice for sorting a linked list. It is relatively easy to implement a merge sort in this situation to require only O(1) extra space. On the other hand, a linked list’s slow random-access performance makes some other algorithms, such as quicksort, perform poorly and others like heap sort completely impossible.
• We can parallelize the merge sort’s implementation due to the divide-and-conquer method, where every smaller sub-problem is independent of each other.

Merge Sort Visualisation

Working of Merge sort Algorithm

Suppose the function mergeSort(int A[], int l, int r) sorts the entire array A[] where we are passing the left index l and right index r as an input parameter.

• Divide Part : Calculating the mid-value, mid = l + (r — l)/2
• Conquer Part 1: Recursively calling the same function to sort the left half of input size n/2, i.e., mergeSort(A, l, mid). We are passing mid as the right index.
• Conquer Part 2: Recursively calling the same function to sort the right half of input size n/2, i.e., mergeSort(A, mid+1, r). We are passing mid +1 as the left index.
• Combine Part: Inside the function mergeSort(), we use the function merge(A, l, mid, r) to merge both the sorted halves into a single sorted array.
• Base Case: If we find l==r during the recursive calls, then the sub-array has at most one element left, which is already sorted. Our recursion will not go further and return from here. In other words, The sub-array of size one is the smallest version of the sorting problem for which recursion directly returns the solution.

Merge Sort pseudo-code:

void mergeSort(int A[], int l, int r)
{

if( l >= r )
return
int mid = l + (r — l)/2
mergeSort(A, l, mid)
mergeSort(A, mid + 1, r)
merge(A, l, mid, r)
}

Overall Merge Sort is an important concept to understand when it comes to algorithms. Thank you for reading this blog post.