Se dă un șir cu n elemente, numere întregi. Folosind metoda MergeSort (Sortare prin interclasare), ordonați crescător elementele acestui șir.
Date de intrare
Programul citește de la tastatură numărul n, iar apoi cele n elemente ale șirului.
Date de ieșire
Programul va afișa pe ecran elementele șirului sortat, separate prin exact un spațiu.
Restricții și precizări
1 ≤ n ≤ 100.000
elementele șirului vor fi cuprinse între -1.000.000.000 și 1.000.000.000
Exemplu
Intrare
12
10 0 -1 -3 1 -4 9 3 -1 -4 3 -4
Ieșire
-4 -4 -4 -3 -1 -1 0 1 3 3 9 10
SOLUTIE
#include <iostream>
using namespace std;
int v[100001],s[100001],n;
void mergesort(int st,int dr)
{
if(st<dr)
{
int m=(st+dr)/2;
mergesort(st,m);
mergesort(m+1,dr);
int i=st;
int j=m+1;
int y=0;
while(i<=m&&j<=dr)
{
if(v[i]<v[j])
{
s[y]=v[i];
i++;
y++;
}
else
{
s[y]=v[j];
j++;
y++;
}
}
while(i<=m)
{
s[y]=v[i];
i++;
y++;
}
while(j<=dr)
{
s[y]=v[j];
j++;
y++;
}
for(int i=st,j=0;i<=dr;i++,j++)
v[i]=s[j];
}
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)
cin>>v[i];
int st=0;
int dr=n-1;
mergesort(st,dr);
for(int i=0;i<n;i++)
{
cout<<s[i]<<" ";
}
return 0;
}