# Merge Sort implementation

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;
}``````

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

`cout << arr[i] << endl;`

Now it’s showing Time limit exceeded

Use scanf() and printf(), may refer this solution: http://www.codechef.com/viewsolution/5458539 or this thread: http://discuss.codechef.com/questions/58286/tsort-used-quick-sort-onlogn

1 Like

Counting sort should work fine for Turbo sort.

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