Merge Sort Algorithm

In this blog post, we will learn about Merage sort algo. which is widely used in computer science.

Merge Sort is a popular comparison-based sorting algorithm that follows the divide-and-conquer paradigm. It was designed by John von Neumann in 1945. The key idea behind Merge Sort is to divide the unsorted list into n sublists, each containing one element, and then repeatedly merge sublists to produce new sorted sublists until there is only one sublist remaining, which is the sorted list.

Here's a step-by-step explanation of the Merge Sort algorithm:

1. Divide: Divide the unsorted list into n sublists, each containing one element. This is the base case of the recursion.

2. Conquer: Recursively sort each sublist. If the sublist has one element, it is considered sorted.

3. Merge: Merge two sorted sublists to produce a new sorted sublist. This is done iteratively until there is only one sorted sublist remaining, which is the final sorted list.

The time complexity of Merge Sort is O(n log n), where n is the number of elements in the list. This makes it more efficient than some other sorting algorithms, especially for large datasets. However, Merge Sort has a space complexity of O(n) due to the need for additional space to store the merged sublists.

Merge sort is useful for sorting Linked Lists

Stable Algorithm

Recursive structure

Let's Take an Example for Merge Sort 🤓

#include<bits/stdc++.h>
using namespace std;
void Merge(std::vector<int>&arr,int left,int mid,int right){

    int n1 = mid - left + 1;
    int n2 = right - mid;

    // creating temporary arrays
    std::vector<int>left_arr(n1);
    std::vector<int>right_arr(n2);

    // Now copy the data into temporary lerft_arr[] and right_arr[]    
    for(int i = 0; i<n1;i++){
        left_arr[i] = arr[left + i];
    }
    for(int j = 0;j<n2;j++){
        right_arr[j] = arr[mid + 1 + j];
    }

    // Merge the temporary arrays back into arr[left..right]

     int i = 0;        //Initial index of first subarray
     int j = 0;       // Initial index of second subarray
     int k = left;   // Initial index of merged subarray

     while(i<n1 && j<n2 ){
         if(left_arr[i]<= right_arr[j]){
             arr[k] = left_arr[i];
             i++;
             k++;
         }
         else{
             arr[k] = right_arr[j];
             j++;
             k++;
         }

     }

    // Copy the remaining elements of left_arr[], if there are any  
    while(i<n1){
        arr[k] = left_arr[i];
        i++;
        k++;
    }

    while(j<n2){
        arr[k]  = right_arr[j];
        j++;
        k++;
    }
}

void mergeSort(std::vector<int>&arr,int left,int right){
        if(left<right){

        int mid = left + (right - left)/2;

        // Now Sorting first and second halves 
        mergeSort(arr,left,mid);
        mergeSort(arr,mid+1,right);


        //  Merge the Sorted halves
        Merge(arr,left,mid,right);
    }
}

int main(){  
    std::vector<int>arr ={38, 27, 43, 3, 9, 82, 10} ;
    int n = arr.size();
    std::cout << "Original array" << std::endl;
    for(int i:arr){
        std::cout << i <<" "<< std::endl;
    }

    std::cout << std::endl;

    //Perfomr Merge short

     mergeSort(arr,0,n-1);

    std::cout << "Sorted Array: " << std::endl;
    for(int i :arr){
        std::cout << i <<" "<< std::endl;
    }

    std::cout << std::endl;

    return 0;
}

Merge Sort is an important concept to understand when comes to programming

If you want to visualize the step-by-step procedure of Merger sort or any other sorting algo I recommend that check out this amazing website

Thank you for reading my content. Be sure to follow and comment on what you want me to write about next 🤓