Merge Sort Implementation in C++

Merge Sort is a technique in which we use the algorithm of divide and conquer.
The input array is first divided into smaller sub-arrays, which are sorted in turn and again merged to get the original array in a sorted manner.

Lets see how it works :

This is our original array

24,56,12,34,3,78,32,9

Now we divide it into two parts :

24,56,12,34           3,78,32,9

Further these parts are sub divided ,

24,56      12,34           3,78    32,9

Then each part is sorted individually

24,56      12,34           3,78    9,32 

Again these sub parts are merged in sorted manner

24,56  +   12,34           3,78   +   9,32 

12,24,34,56      +       3,9,32,78

3,9,12,24,32,34,56,78

#include <iostream>

using namespace std;

void merge(int*,int*,int,int,int);

void mergesort(int *a, int*b, int low, int high)

{

    int pivot;

    if(low<high)

    {

        pivot=(low+high)/2;

        mergesort(a,b,low,pivot);

        mergesort(a,b,pivot+1,high);

        merge(a,b,low,pivot,high);

    }

}

void merge(int *a, int *b, int low, int pivot, int high)

{

    int h,i,j,k;

    h=low;

    i=low;

    j=pivot+1;

    while((h<=pivot)&&(j<=high))

    {

        if(a[h]<=a[j])

        {

            b[i]=a[h];

            h++;

        }

        else

        {

            b[i]=a[j];

            j++;

        }

        i++;

    }

    if(h>pivot)

    {

        for(k=j; k<=high; k++)

        {

            b[i]=a[k];

            i++;

        }

    }

    else

    {

        for(k=h; k<=pivot; k++)

        {

            b[i]=a[k];

            i++;

        }

    }

    for(k=low; k<=high; k++) a[k]=b[k];

}

int main()

{

    int a[] = {12,10,43,23,-78,45,123,56,98,41,90,24};

    int num;

    num = sizeof(a)/sizeof(int);

    int b[num];

    mergesort(a,b,0,num-1);

    for(int i=0; i<num; i++)

        cout<<a[i]<<" ";

    cout<<endl;

}

Share on Facebook Share on Twitter Share on Google Plus

About Engr. Rokon Khan