Envío 1925

Código

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#include <set>
#include <list>
#include <map>
#include <vector>
#include <stack>
#include <algorithm>
#define forn(a, n) for(int a = 0; a<(int) (n); ++a)
#define rforn(a, n) for(int a = (n)-1; a>=0; --a)
using namespace std;
const int N = 6e5+20;

/*
void partition(int a[], int low, int high)
{
    int pivot = a[high];
    int i = low-1;

    for(int j = low; j < high; j++)
    {
        if(a[j] < pivot)
        {
            i++;
            swap(a[j], a[i]);
        }
    }
}

void quicksort(int a[], int low, int high)
{
    if(low < high)
    {
        int pi = partition(a, low, high);
        quicksort(a, low, pi-1);
        quicksort(a, pi+1, high);
    }
}
*/

void merge(int a[], int l, int m, int r)
{
    int n1 = m-l+1;
    int n2 = r-m;
    int L [51000];
    int R [51000];

    for(int i = 0; i < n1; i++) L[i] = a[l+i];
    for(int i = 0; i < n2; i++) R[i] = a[m + 1 + i]; 

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

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

    while (i < n1)
    {
        a[k] = L[i];
        i++;
        k++;
    }
    while (j < n2)
    {
        a[k] = R[i];
        j++;
        k++;
    }
}

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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, pos, temp, este, low, high;
    cin>>n;
    int a [1001];
    //vector <int> a;
    for(int i = 0; i < n; i++)
    {
        cin>>a[i];
        //cin>>este;
       //a.push_back(este);
    }
    

    // --- QUICK SORT --- -> ordena entre menor y mayor de pivot, luego ordena en cada mitad lo menor y lo mayor de nuevos pivots
    /*
    low = 0;
    high = n-1;
    quicksort(a, low, high);
    */


    // --- MERGE SORT --- -> parte en mitades, después cada mitad la parte en mitas. al final arma a partir del menor de cada mitad
    mergeSort(a, 0, n-1);

    for(int i = 0; i < n; i++)
    {
        cout<<a[i]<<" ";
    }
    cout<<endl;
}