Design and Analysis of Algorithms

Vegesna Eshita Raj

Merge Sort Algorithm

Merge Sort is based on the Divide and Conquer Algorithm and is one of the most popular and efficient sorting algorithms. It splits the given list into two equal halves, then calls itself for each half and merges the two sorted parts. Using this technique, we can divide the list into equal halves until it can’t be divided any further. In case of only one element in the list, the sorting is done by definition. Then it joins the smaller sorted lists together, keeping the resultant list sorted as well. The sub-lists are divided into halves again and again until the list can no longer be divided. Then we merge the two one-element lists into a two-element list during the sorting time. The sorted two-element pairs are combined into four-element lists, and so on, until the sorted list is obtained. To perform the merging, we must define the merge() function.

Here are the steps to explain how it works:

Step 1: Return if there is only one entry in the list that has already been sorted.

Step 2: Recursively divide the list into two parts until it can no longer be divided.

Step 3: Sort the smaller lists and merge them into a new list.

When it comes to the time and space complexity, it is mentioned below:

It has an overall time complexity of O(nlogn).In terms of efficiency, it is better because the worst-case runtime is also O(nlogn).

It has a space complexity of O(n). This signifies that this technique consumes a lot of memory and may cause operations for the most recent data sets to slow down.