Merge Sort

Most efficient method of sorting.

What is Merge Sort?

Merge sort is a divide-and-conquer algorithm based on the idea of breaking down a list into several sub-lists until each sub-arrays consists of a single element and merging those sub-arrays in a manner that results into a sorted list.

Basic steps to be followed:

1. Divide the array in 2 different parts. We will be dividing the array into sub-arrays till the sub-array will contain only one element, which will eventually mean that this sub-array would be sorted.
2. Sort these 2 different arrays using recursion.
3. Merge these 2 sorted arrays.

Ideas behind merging the array:

While comparing two sub-arrays for merging, the first element of both sub-arrays that is left and right sub-array is taken into consideration. While sorting in ascending order, the element that is of a lesser value becomes a new element of the sorted list. This procedure is repeated until both the smaller sub-arrays are empty and the new combined sub-array comprises all the elements of both the sub-array.

Graphical representation of the working of merge sort:

Source

Merge sort visualiser :

Let us have a deeper understanding of the concept of merge sort using the visualiser given below:

Merge Sort visualize | Sorting | Algorithms | HackerEarth

C++ code for merge sort:

#include<iostream>
using namespace std;
//Declaring the array as global so that we don't need to pass it as parameter in the
//recursive function
const int N = 1e5+10;
int a[N];   //Array which is merged 

//Function to merge the array
void merge(int l,int r,int mid)
{
    //First we need to divide the array into 2 parts that is left and right subarray
    //Left subarray : From l to mid
    //Right subarray : From mid+1 to r
    int l_sz = mid-l+1;
    int r_sz = r-mid;

    //Declaring the size of L and R array as size+1 so that the last element can be 
    //inserted as INT_MAX
    int L[l_sz+1];
    int R[r_sz+1];

    //Copying elements from array "a" into left subarray
    for(int i=0;i<l_sz;++i)
    {
        L[i] = a[i+l];
    }

    ////Copying elements from array "a" into right subarray
    for(int i=0;i<r_sz;++i)
    {
        R[i] = a[mid+1+i];
    }

    //setting the last element of array L and R as INT_MAX
    L[l_sz] = R[r_sz] = INT_MAX;

    //lp and rp are pointer which will help to maintain the indices during merging
    int lp = 0;
    int rp = 0;

    //Comparing the values in the L and R array and merging them and placing the sorted 
    //elements in the array "a"
    for(int i=l;i<=r;++i)
    {
        if(L[lp]<=R[rp])
        {
            a[i] = L[lp];
            lp++;
        }

        else
        {
            a[i] = R[rp];
            rp++;
        }
    }
}

//recursive function of mergesort
void mergesort(int l,int r)
{
    //base case when l==r means only one element is present in the array so the array is sorted
    if(l==r) return;
    int mid = (l+r)/2;   //Note : Here take the mid term as (l+r)/2 only instead of (l+(r-l))/2
    mergesort(l,mid);  //sorting the left subarray
    mergesort(mid+1,r); //sorting the right subarray
    merge(l,r,mid);  //merging the array
}

int main()
{
    //Input for number of elements in the array
    int n;
    cout << "Enter number of elements : ";
    cin >> n;

    //Taking input for the array which is to be sorted
    cout << "Enter the elements of the array : ";
    for(int i=0;i<n;++i)
    {
        cin >> a[i];
    }

    //calling the function which will sort the array
    mergesort(0,n-1);

    //Displaying the sorted array
    cout << "Sorted array is : ";
    for(int i=0;i<n;++i)
    {
        cout << a[i] << " ";
    }

    return 0;
}

JAVA code for merge sort:

public class Main
{
    static void mergeSort(int arr[], int start, int end){  
        //Recursive method, to divide the given array into a single sorted element.
        
        
        if(start>=end){     //Base case for the recursion.
            return;
        }
        
        int mid = start + ((end - start)/2);        //Calculating the middle index for division.
        
        //Function call for the first half:
        mergeSort(arr,start,mid);  
        
        //Function call for the second half:
        mergeSort(arr,mid+1,end); 
        
        //Merging the 2 sorted arrays:
        merge(arr, start, end, mid);
    }
    
    static void merge(int arr[], int start, int end, int mid){
        //Function that will merge already sorted arrays:
        
        
        int i = start;
        int j = mid+1;
        int k = 0;
        
        int res[] = new int[end - start + 1];       //Merged array declaration
        
        //Comparing elements from both halves and inserting the smaller value in merged array.
        while(i<=mid && j<=end) {
   if(arr[i]<=arr[j]) {
    res[k++] = arr[i++];
   }
   else {
    res[k++] = arr[j++];
   }
  }
  
  //If elements of the 1st half are remaining:
  
  while(i<=mid) {
   res[k++] = arr[i++];
  }
  
  //If elements of the 2nd half are remaining:
  
  while(j<=end) {
   res[k] = arr[j];
   j++;
   k++;
  }
  
  //Copying the values from the merged array to our array:
  
  for(int i1=0,j1=start; i1<res.length; i1++,j1++) {
   arr[j1] = res[i1];
  }
    }
    
 public static void main(String[] args) {
     //Declaring the array to be sorted.
  int arr[] = {4,7,8,2,3,1,6,5};
  
  //Calling the method to sort the array.
  mergeSort(arr,0,7);
  
  
  //Displaying the sorted array:
  
  for(int i=0; i<arr.length; i++){
      System.out.print(arr[i] + " ");
  }
 }
}

Time Complexity:

The list of size N is divided into a max of log N parts, and the merging of all sub-array into a single array takes O(N) time, the worst case run time of this algorithm is O(n(log n)).

For queries regarding the content, please drop a mail to loop@cumminscollege.in Links for in-depth studying and practice problems are sent via mail to students of the college on the date of publishing of the blog by Loop Club. The content is a part of DSA Bulletins started by Team Loop, to provide thorough knowledge and facilitate the learning of new topics of DSA. We are a group of students who are passionate about CP and DSA and want to create awareness and help students in the above topics.