Featured Post

Trie implementation in C

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;
}

Comments

  1. You should be passing in a *b with the same length as a instead.

    ReplyDelete
  2. very useful during my exam times man....thanks...!!

    ReplyDelete
  3. Best explanation on the merge sort algorithm. Thanks.

    ReplyDelete
  4. You might want to declare the size of the 'a' array as a constant like:
    const int num=sizeof(a)/sizeof(int);
    and then it works perfectly.

    ReplyDelete
  5. I have to say the code is full of bugs and badly written.

    ReplyDelete
  6. Replies
    1. It would be great if you could let me know specifically whats wrong with this program. I would try to sort it out.

      Delete
  7. I did'nt get any bugs....
    its a gud and clean program..
    thank you VARUN...

    ReplyDelete
  8. I could use more comments! what is int h? j?

    ReplyDelete
    Replies
    1. These are variables used to traverse, please check their initialization.

      Delete
  9. Hi, Can you please explain to me why do we need extra checks like if(h>pivot)? Is it for all the remaining elements for the right array just in case the left and right array are not symmetric?

    ReplyDelete
  10. Hi,
    I also noticed that the array b is not required, we can just declare it as temporary variable (as declared in the main) in the merge function itself.

    ReplyDelete
  11. very helpful in DAA lab.. thankyou. it helps to fool our teacher that we are studying :P :D

    ReplyDelete
    Replies
    1. Who does it "help"? Certainly not yourself!

      Delete
  12. really nice merge sort implementation

    ReplyDelete
  13. Thx a lot its 100x time better then our prof pseudo code think can understand it much better xD

    ReplyDelete

Post a Comment

Please post your valuable suggestions