Merge Sort

#include <stdio.h>

#include <iostream>

 

 

using namespace std;

 

int arr[100000];

 

void merge(int lw,int mid,int hi)

{

int L[mid-lw+1];

int R[hi-mid+1];

int tmp;

for(int i=0;i<mid-lw+1;i++)

L[i]=arr[lw+i];

for(int i=0;i<hi-(mid+1)-1;i++)

R[i]=arr[mid+i+1];

int i = 0;

int j = 0;

int k = lw;

while(i<(mid-lw+1) && j<(hi-mid))

{

if(L[i]<=R[j])

{

arr[k]=L[i];

i++;

k++;

}

else if(L[i]>R[j])

{

arr[k]=R[j];

k++;

j++;

}

}

while(i<(mid-lw+1))

{

arr[k++]=L[i++];

}

while(j<(hi-mid))

{

arr[k++]=R[j++];

}

}

 

void mergesort(int lw,int hi)

{

if(hi>lw)

{

int mid=lw+(hi-lw)/2;

mergesort(lw,mid);

mergesort(mid+1,hi);

merge(lw,mid,hi);

}

}

 

int main()

{

int t,n;

scanf("%d",&t);

while(t--)

{

scanf("%d",&n);

for(int i=0;i<n;i++)

scanf("%d",&arr[i]);

mergesort(0,n-1);

for(int i=0;i<n;i++)

cout<<arr[i]<<" ";

}

return 0;

}