Wednesday, December 14, 2016

Merge Sort in c++

#include<iostream>
#include<vector>
using namespace std;
 
void merge(vector<int> &v,int l, int m,int r)
  {
    vector<int> a(v.begin()+l,v.begin()+m+1);
    vector<int> b(v.begin()+m+1,v.begin()+r+1);
    int ptr1=0,ptr2=0,ptr=l;
    while(ptr1<a.size() && ptr2<b.size())
        if(a[ptr1]<b[ptr2])
            v[ptr++]=a[ptr1++];
        else
            v[ptr++]=b[ptr2++];
    while(ptr1<a.size())
        v[ptr++]=a[ptr1++];
    while(ptr2<b.size())
        v[ptr++]=b[ptr2++];
  }

void mergesort(vector<int> &vec,int l,int r )
   {
      if(l<r)
       {
           int m=(l+(r-1))/2;
           mergesort(vec,l,m);
           mergesort(vec,m+1,r);
           merge(vec,l,m,r);
       }
   }

int main()

  {

    int arr[] ={99,8,22,11,44,55,2,1,5,26,98,8,888,36,99,75,48,74,587,4};
    vector<int> vec(arr,arr+sizeof(arr)/sizeof(int));
    mergesort(vec,0,(vec.size())-1);
    for(int i=0;i<vec.size();i++)
        cout<<vec[i]<<" ";
    return 0;

  }