Merge Sort implementation

general
,
1

I was trying to implement Merge Sort and when I submitted this on Turbo Sort to check wheter it’s correct but it gave me wrong answer. What is wrong in this ?

#include <iostream>
using namespace std;

void merge(int arr[], int l , int m , int r)
{
	int i,j,k;
	int n1 = m - l + 1;
	int n2 = r - m ;
	int L[n1];
 	int R[n2];
	for(int i = 0 ; i < n1 ; i++)
	{
		 L[i] = arr[l+i];
	} 
	for(int j = 0 ; j < n2 ; j++)
	{
		 R[j] = arr[m+1+j];
	}

	i = 0;
	j = 0;
	k = l;

	while(i < n1 && j < n2)
	{
		if(L[i] <= R[j])
		{
			arr[k] = L[i];
			i++;
		}
		else
		{
			arr[k] = R[j];
			j++;
		}
		k++;
	}

	while(i < n1)
	{
		arr[k] = L[i];
		i++;
		k++;
	}

	while(j < n2)
	{
		arr[k] = R[j];
		j++;
		k++;
	}

}

void mergeSort(int arr[] ,int l , int r)
{
	if(l < r)
	{
		int m = l+(r-l)/2;
		mergeSort(arr , l , m);
		mergeSort(arr , m+1 , r);
		merge(arr, l , m , r);
	}
}



int main()
{
	int total;
	cin >> total;

	int arr[total];
	for(int i = 0 ; i < total ; i++)
	{
		cin >> arr[i];
	}

	mergeSort(arr , 0 , total-1);

	for(int i = 0 ; i < total ; i++)
	{
		cout << arr[i];
	}
	cout << endl;
}
2

You need to print each number in a new line after sorting. Add “endl” inside the last loop like this

cout << arr[i] << endl;

3

Counting sort should work fine for Turbo sort.

Here: CodeChef: Practical coding for everyone

4

Now it’s showing Time limit exceeded :frowning:

5

Use scanf() and printf(), may refer this solution: CodeChef: Practical coding for everyone or this thread: http://discuss.codechef.com/questions/58286/tsort-used-quick-sort-onlogn

1 Like
6

Follow the approach of @damn_me, it will get AC, check here.