MERGE SORT IMPLIMENTATION

i am not able to impliment merg-esort prpperly.... so some1 plzz help me out with my code....

here my code goes :-

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
void devide(ll[],ll,ll);
void merge(ll[],ll,ll,ll);
int main()
{
	long long int t;
	cin>>t;
	while(t--)
	{
		ll n;
		cin>>n;
		ll a[n],i;
		for(i=0;i<n;i++)
		{
            cin>>a[i];
		}
		devide(a,0,n-1);
		for(i=0;i<n;i++)
		{
            cout<<a[i]<<" ";
		}
		cout<<"\n";
	}
	return 0;
}
void merge(ll a[],ll l,ll m,ll r)
{
	ll n1,n2;
	n1=m-l+1;
	n2=r-m;
	ll L[n1],R[n2],i=0,j=0,k=0;
	for (i =0;i<n1;i++)
	{
        L[i]=a[l+i];
    }
    for (j=0;j<n2;j++)
    {
	    R[j]=a[m+1+j];
    }
        i=0;j=0;k=0;
	while(i<n1 && j<n2)
	{
		if(L[i]<=R[j])
		{
			a[k]=L[i];i++;
		}
		else
		{
			a[k]=R[j];j++;
		}
		k++;
	}
	while(i<n1)
	{
		a[k]=L[i];i++;k++;
	}
	while(j<n2)
	{
		a[k]=R[j];j++;k++;
	}
}
void devide(ll a[],ll l,ll r)
{
	
	if(l<r)
	{
		ll m;
		m=l+(r-l)/2;
		devide(a,l,m);
		devide(a,m+1,r);
		merge(a,l,m,r);
	}
}

merge-sort

Asked by: ABHISHEK_KUMAR2 on April 7, 2019, 6:34 p.m. Last updated on April 7, 2019, 6:34 p.m.

1 Answer(s)

there's a mistake in your merge function.

        i=0;j=0;k=l; //k will be set to l(small L) not 0 
	while(i<n1 && j<n2)
	{
		if(L[i]<=R[j])
		{
			a[k]=L[i];i++;
		}
		else
		{
			a[k]=R[j];j++;
		}
		k++;
	}

Shubham_Kumar_Gupta last updated on April 7, 2019, 6:34 p.m. 0 Reply Upvote

Instruction to write good question

1. Write a title that summarizes the specific problem
2. Pretend you're talking to a busy colleague
3. Spelling, grammar and punctuation are important!

Bad: C# Math Confusion
Good: Why does using float instead of int give me different results when all of my inputs are integers?
Bad: [php] session doubt
Good: How can I redirect users to different pages based on session data in PHP?
Bad: android if else problems
Good: Why does str == "value" evaluate to false when str is set to "value"?

Refer to Stack Overflow guide on asking a good question.

MERGE SORT IMPLIMENTATION

Enter your answer details below:

Enter your comment details below:

1 Answer(s)

Instruction to write good question