Home » Merge Sort algorithm | Data Structures

AlgorithmsData structures

Merge Sort algorithm | Data Structures

Arpit Jain

May 6, 2021

0

SaveSavedRemoved 0

Merge Sort algorithm

Merge sort algorithm is a sorting algorithm that works on the divide and conquers strategy. It divides the input list into parts and arranges them to make a sorted list by merging them again. If we have two lists that are already sorted then we use merge sort to merge these two lists and make a complete sorted list. The time complexity of merge sort is in order of nlogn i.e. O(n logn).

Topics Covered

1. Types of merge sort
2. Algorithm for different ways
3. Example of merge sort
4. Advantages and disadvantages

Merging can be of many types. example

• 2-way merging – merging of two lists
• 4-way merging – merging of four lists
• m-way merging – merging of m lists

Algorithm for merging of two lists A & B which consists of m & n elements respectively.

algorithm mergesort(A,B,m,n)
{
    i=1, j=1, k=1, C;
    while(i<=m && j<=n)
    {
        if (A[i] < B[j])
            C[k++] = A[i++];
        else
            C[k++] = B[j++];
     }
     for(;i<=m; i++)
            C[k++] = A[i];
     for(;j<=n; j++)
            C[k++] = B[j];
}

Example of 2-way merge sort:

In the given example,

In each step, time taken is n.

No. of total steps is logn.

So, the time taken in merge sort is n*logn.

code to use merge sort in program

l=array[1] , h=array[n];
algorithm mergesort(l,h)
{
   if (l<h)
    {
       mid=(l+h)/2;
       mergesort(l,mid);
       mergesort(mid+1,h);
       mergesort(l,mid,h);
    }
}

Advantages and Disadvantages of merge sort algorithm

1. Advantages

a.) Large size list:

Merge sort is used in sorting of very large amount of files or to sort very high memory data files.

b.) Linked List:

We can merge two linked lists using merge sort without creating a third linked list by just changing their node, pointers and addresses.

c.) External Sorting:

Assume, we have two files of 5GB & 10GB and we have to merge them, but we have only 4GB RAM in our system. So, we copy the data in pieces from the files and then merge them. After merging we copy the pieces into the main big file. That’ how merge sort is used in external sorting.

d.) Stable:

It is stable in nature and arranged the data in proper order. Merge sort never changes the order of the previous data.

2. Disadvantages

a.) Extra Space: Merge sort algorithm uses extra space in sorting.

b.) Not suitable for small problems:

Merge sort algorithm works best for bigger algorithms. It takes greater time for shorter algorithms(or small data) than compare to the other sorting methods but takes lesser time for larger algorithms than compare to others.

Example:

Insertion Sort – O(n²)

Merge Sort – O(n logn)

So, merge sort is better than insertion sort at n>=15. So, we used insertion sort in place of merge sort for small amount of data.

c.) Recursive:

It will acquire n+logn space in stack. { n for extra space and logn for merging space }