Posts

Showing posts from April, 2017

C++ STL: Merge_Sort using Vector (Sorting)

#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;
void merge_(vector<int>& v,int p,int q,int r){
int n1=q-p+1;  int n2=r-q;// here n1 was written as q+p+1
vector<int>L(n1);
vector<int>R(n2);
for(int i=0;i<n1;i++){
    L[i]=v[p+i];
}
for(int j=0;j<n2;j++){
    R[j]=v[q+j+1];
}
int i=0,j=0;
int k;// declaring k outside
for( k=p;k<=r && i<n1 && j < n2;k++){// if i >= n1 || j> = n2 then it will access random memory
    if(L[i]<=R[j]){
        v[k]=L[i];
        i++;
    }
    else{
        v[k]=R[j];
        j++;
    }
}
for(i = i;i<n1;++i)// these are the two loops must be there if L or R runs out
{
    v[k] = L[i];
    k++;
}