Merge Sort

Merge Sort is a regularly used sorting method in computer science. Merge Sort is a divide-and-conquer approach to sorting. It works by breaking down an issue into two or more sub-problems of the same or related type until they are simple enough to tackle directly. The sub-problems’ solutions are then integrated to produce a solution to the original problem. As a result, Merge Sort splits the array into equal parts before combining them in a sorted way.

How it works ?

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

Functions involved

1. The merge() is used for merging two halves
2. The mergesort() function recursively calls itself to divide the array till size becomes one.

Algorithm

Algorithm

Here arr is the given array, beg is the starting element and end is the last element of the array. The important part of the merge sort is the MERGE function. This function performs the merging of two sorted sub-arrays that are A[beg…mid] and A[mid+1…end], to build one sorted array A[beg…end]. So, the inputs of the MERGE function are A[], beg, mid, and end.

Example how merge Sort works

Here the picture explains clearly how merge sort works for an unsorted array, we can observe it constantly divide the subarray into halves until it becomes one element and sorts it. Finally sorts the two halves.

Characteristics of Merge Sort

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

Overall Merge Sort is an important concept to understand when it comes to algorithms. Thank you for reading this blog post. In upcoming blog posts of this series, I will go over other sorting algorithms like quick sort.