How to implement merge sort using C++ and time complexity

merge-sort
Spread the love

Merge Sort is a Divide and Conquer algorithm. It divides the input array into two halves, calls itself for the two halves, and then merges the two sorted halves. The merge() function is used for merging two halves. Merge sort is also like the quick sort algorithm. In this tutorial, I will show you how to implement a merge sorting algorithm using C++.

Divide-and-conquer algorithm

 In computer science, divide and conquer is an algorithm design paradigm. The divide-and-conquer algorithm recursively breaks down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly.

Well, implement the merge sorting algorithm you need two functions. One is merge_sort and another one is merge. The backbone of this sorting algorithm is the merge function.

Let’s see the merge_sort function. I will explain you below.

void merge_sort(int A[], int lb, int ub)
{
    if (lb < ub)
    {
        int mid = (lb + ub) / 2;
        merge_sort(A, lb, mid);
        merge_sort(A, mid + 1, ub);
        merge(A, lb, mid, ub);
    }
}

This is our merge_sort function, which is a simple function. You can see that this function takes three parameters. The first one is an array that we have to sort, the second parameter is the lower bound and the last parameter is the upper bound. First, you have to check a condition with the lower bound is greater than the upper bound. If the conditions are satisfied then you have to calculate mid-value. Then call again the merge_sort function and its parameter will be the array and the lower bound and the mid-value. After then you have to call again the merge_function and its parameters will be the array and the mid + 1 and the upper bound.

Then, You have to call the merge function with parameters the array and the lower bound and the mid-value as well upper bound. I told you before that the backbone of this merge sort algorithm is the merge function. Let’s see the merge function, I will explain you below.

void merge(int A[], int lb, int mid, int ub)
{
    int i = lb;
    int j = mid + 1;
    int k = lb;

    while (i <= mid && j <= ub)
    {
        if (A[i] >= A[j])
        {
            B[k] = A[i];
            i++;
        }
        else
        {
            B[k] = A[j];
            j++;
        }
        k++;
    }

    if (i > mid)
    {
        while (j <= ub)
        {
            B[k] = A[j];
            j++;
            k++;
        }
    }
    else
    {
        while (i <= mid)
        {
            B[k] = A[i];
            i++;
            k++;
        }
    }

    for (int k = lb; k <= ub; k++)
    {
        A[k] = B[k];
    }
}

Well, inside this function first I took a couple of variables then store the values which I passed by parameter. If you are familiar with the how-to merge two sorted arrays then this portion will be easy for you.

Time Complexity

Sorting arrays on different machines. Merge Sort is a recursive algorithm and time complexity can be expressed as following recurrence relation. 
T(n) = 2T(n/2) + θ(n)

Applying the master theorem we can measure the time complexity of merge sort is O(nlogn).

Full Code:


#include <bits/stdc++.h>
using namespace std;

int B[100];
void print_array(int A[], int n)
{
    cout << endl;
    for (int i = 0; i < n; i++)
    {
        cout << A[i] << " ";
    }
    cout << endl;
}
void merge_asc(int A[], int lb, int mid, int ub)
{
    int i = lb;
    int j = mid + 1;
    int k = lb;

    while (i <= mid && j <= ub)
    {
        if (A[i] >= A[j])
        {
            B[k] = A[i];
            i++;
        }
        else
        {
            B[k] = A[j];
            j++;
        }
        k++;
    }

    if (i > mid)
    {
        while (j <= ub)
        {
            B[k] = A[j];
            j++;
            k++;
        }
    }
    else
    {
        while (i <= mid)
        {
            B[k] = A[i];
            i++;
            k++;
        }
    }

    for (int k = lb; k <= ub; k++)
    {
        A[k] = B[k];
    }
}

void merge_sort(int A[], int lb, int ub)
{
    if (lb < ub)
    {
        int mid = (lb + ub) / 2;
        merge_sort(A, lb, mid);
        merge_sort(A, mid + 1, ub);
        merge_asc(A, lb, mid, ub);
    }
}

int main()
{
    int A[] = {10, 2, 5, 7, 3, 4};
    int n = 6;
    print_array(A, n);
    merge_sort(A, 0, n - 1);
    print_array(A, n);
    return 0;
}

Spread the love

About Anisur Rahman Shahin

Hello. My name is Shahin. I'm a tech enthusiast guy. Personally, I’m Optimistic and always in hurry kinda person. I'm a freelance web developer. I am working at Zakir Soft as Laravel Developer. My Portfolio website: https://devshahin.com/

View all posts by Anisur Rahman Shahin →

Leave a Reply

Your email address will not be published.