Merge Sort

Sorting is the process that is used to arrange the elements in a specific manner. A sorting algorithm is used to rearrange a given array according to the specific order. It can sort an array in either ascending or descending order. We need a sorting algorithm because it helps us to easily and fastly locate elements in the array list. The key purpose of sorting algorithms is to get the record simpler to find, add, and remove. There are different types of sorting algorithms such as :

• Selection Sort.
• Insertion Sort.
• Radix Sort.
• Bubble Sort.
• Merge Sort.
• Heap Sort.
• Quick Sort.

Merge sort is a sorting algorithm that is used to sort the sequence of elements. Firstly, the sequence is divided into subgroups. Once the division is complete, then these divided groups are combined. During the combining process, each group’s numbers are organized so that they are arranged from smallest to largest after combination. When groups with several numbers have been combined it the first numbers are compared.

In this, an unsorted array list is divided into two parts, this is repeated until all the elements are separated. The elements are then compared in pairs and placed into sorted order and combined. This process is repeated until the list is recompiled into one sorted list.

Merge sort is a sorting algorithm that operates by repeatedly breaking the given array into a sub-array. And then breaking them into further sub-arrays. When the size of sub-arrays becomes one, then we will merge them to get a sorted array. Merge sorting is done recursively.

Its worst-case time complexity is ‘O ( n log log n )’.

Working Principle

Merge sort is an effective sorting algorithm. It works on the ‘’Divide and Conquer’’ technique.

• Divide: It involves the splitting input array list into two lists of similar size.
• Conquer: It involves the sorting of both sub-lists recursively.
• Merge: It involves merging both sorted sublists into one sorted list.

In this technique, the large problem is divided into smaller parts and then those small parts can be easily conquered and then they can be merged back to get the final result. In this, the whole array is divided into ’n’ sublists. Each sub-list will have one element. And we will keep on dividing the sub list until we get a sub-list with one element. Then finally we combine each of the sub-lists and this sub-list combing process continues until we get a new sorted sub-list. And we keep merging the sub-lists until we get a final complete sorted list.

Its working principle involves following major steps:

• Divide the given array into a sub-list.
• Merge sub-lists for getting one complete sorted list.

Let us take an array having five elements from 0 to 4.This array will be divided into two( left and right ) parts. The array on the left part contains 2 elements while the right part contains 3 elements. The left part will also be divided into two subparts and then we get two single sub-lists. Once we get sorted sublists for the left part then they will be merged into a single sorted left array.

Now, we will sort the array on the right part by firstly dividing it into two further parts. The right part will now contain further two parts i.e. left and right subparts. The left subpart contains only one element while the right subpart contains two elements. The left part is already sorted. So we will now sort the right part by dividing it into two subparts. Now, these two sorted subparts of the right part will be merged. Then left and right sorted subparts of the right side will be merged into a single sorted right array. Finally, we will get a single sorted array/list by merging the left and right sorted array.

Example

To understand this concept, let us consider an array ‘B’ that is given below. This array has a total of nine elements.

We will divide this array into two sub-arrays. For this purpose, we will find its midpoint and then divide this array from that mid-point. So, the midpoint will be

So, this array is divided from index 4.Sub arrays will be:

Now we will divide these two sub-lists into further sub-lists to get a sublist with only one element. Again we will the midpoint first for each of the sub-lists.

Midpoint of first sub-list:

Mid-point of second sub-list:

Now, we have four sub-lists. They will be further divided from their midpoints.

Mid-point of 3rd sub-list:

Mid-point for 4th, 5th and 6th sub-list:

There is only one sub-list that has 2 elements. So we will divide that sub-list into further sub-list. And other sub-lists will remain the same because they contain one element each

Mid-point of 7th sub-list:

Now, we will merge these sub-lists. The merging process will be performed by combining the first two elements and comparing them. It can be seen that 5 is less than 15, so we will put 5 first and then 15 in the new sorted sub-list.

Now, this first new sorted sub-list will be compared with the third element which is 24. And second, sorted sublist be:

Then, we will compare the 4th and 5th sub-list elements and it can be seen that 1 is less than 8. So now 1 will be placed first and then 8. After that, we will get 3rd sorted sub-list:

Now this 3rd sorted sub-list will be compared with 2nd sorted sub-list and we will get the 4th sorted sub-list that is:

Similarly, we will merge the 5th sorted sub-list by comparing and merging the 6th and 7th sub-list:

Now, we will get the 6th sorted sub-list by comparing the 8th and 9th sub-list:

Then, we will compare and merge the 5th and 6th sorted sublist to get the 7th sorted sub-list:

Finally, the 4th and 7th sorted sub-list will be compared and merged and the 8th sorted sub-list will get. For this purpose, we will compare the first element of the 4th and 7th sorted sub-list and look for smaller elements. The smaller element will be put first. Then a pointer will be incremented on that sorted sub-list and compared with another sorted sub-list.

Runtime Analysis

The run time of an algorithm is denoted by T(N). There will be two cases:

• First will be the base case when the algorithm will take a constant amount of time that is ‘a’.

• For merge sort to the left and right, time will be :

Where ‘b’ is just a constant. And bN shows that the merge takes some constant amount of time per element being merged.

So, we can write as:

So, the running time of merge sort will be O(N log2 N)

K-Way Merge Sort

It is also known as multiway merging. It is used for external sorting. It has k sorted array input in which each array has ’n’ elements. In this, we will merge sorted arrays to get sorted output.

2-Way Merge Sort

It is used in external merging. It has ’n’ number of elements. Let us consider 2-way merging with the help of an example. In this, two arrays have been taken as input. Each array has four elements. The size of both arrays is four. Both arrays are indexed from 0 to 3. To merge these two arrays, we need a three-pointer that is placed at the starting element of each of the arrays. Both arrays are already in sorted order. On combining these two arrays, we will get a resultant array having eight elements. We will compare the first element of the first two arrays. And smaller elements will be placed first in the output array. Then the pointer of the output array and second array will be incremented and the same process of comparing elements will be continued. Finally, we will get a sorted array at the output.

3-Way Merge Sort

In this, we have three arrays having an equal number of elements and size. Each array has four elements. All of these arrays are in a sorted manner. As the total number of elements in these arrays are 12, we will create an output array having the size of 12 elements. Now we will take four pointers that will be placed at the zeroth index at each of the arrays. Now we will compare the first element in each of the first three arrays. The then smaller element will be placed at the first position in the resultant array. After that, pointers of input and resultant array will be incremented. And the same process will be repeated until we get a sorted array list.

Advantages and Disadvantages of Merge Sort

Advantages:

It has the following benefits:

• It is faster for larger lists relating to insertion and bubble sort because it does not pass through the whole list several times.
• It has a stable running time.
• It could be applied to files of every size.
• It is excellent for arranging slow access data.

Disadvantages:

It has the following disadvantages:

• It is slower for a short list.
• This sorting method needs more space to store information.

Applications

It has the following applications:

• It is used for organizing linked lists in O(nlog n) time.
• It is also used for inversion counting.
• It is used for sorting a large amount of information.