MergeSort

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