CODEWITHSUNDEEP
c++algorithmsorting
coder
coder

Reputation: 37

merge sort sorting partially

for input 6,2,9,1,5,8 i'm getting 1,2,6,9,5,8.This algorithm is written based on https://gist.github.com/mycodeschool/9678029#file-mergesort_c-c-L28 please help me in getting 1,2,5,6,8,9 as the output also point out the mistake here.Thanks in advance.

#include<iostream>
using namespace std;

void merge(int a[],int l[],int lc,int r[],int rc){
  int i,j,k;
  i=0;j=0;k=0;
  while(i<lc && j<rc){
        if(l[i]<r[j]){
          a[k++]=l[i++];
      }
      else{
        a[k++]=r[j++];
     }
    while(i<lc){
        a[k++]=l[i++];
    }
    while(j<rc){
        a[k++]=r[j++];
    }
}
}

void mergesort(int a[],int n){
  int mid;
  if (n<2){
    return;
 }
 mid=n/2;
 int l[mid],r[n-mid];
 for(int i=0;i<mid;i++){
    l[i]=a[i];
 }
 for(int i=mid;i<n;i++){
    r[i-mid]=a[i];
}
mergesort(l,mid);
mergesort(r,n-mid);
merge(a,l,mid,r,n-mid);
}

int main(){
int a[]={6,2,9,1,5,8};
int n=6;
mergesort(a,n);
for(int i=0;i<n;i++){
    cout<<a[i]<<" ";
}
}

Upvotes: 1

Views: 52

Answers (1)

m7mdbadawy
m7mdbadawy

Reputation: 920

your problem is that is that these loops 

while(i<lc){
    a[k++]=l[i++];
}
while(j<rc){
    a[k++]=r[j++];
}

are inside this loop while(i<lc && j<rc) and they should be outside it as you copy the rest of a[] if b[] is done while a[] has some elements and like wise for b[] and this is the whole merge function

void merge(int a[],int l[],int lc,int r[],int rc)
{
    int i,j,k;
    i=0;
    j=0;
    k=0;
    while(i<lc && j<rc)
    {
        if(l[i]<r[j])
        {
            a[k++]=l[i++];
        }
        else
        {
            a[k++]=r[j++];
        }
    }
    while(i<lc)
    {
        a[k++]=l[i++];
    }
    while(j<rc)
    {
        a[k++]=r[j++];
    }
}

Upvotes: 1

Related Questions