Cod sursa(job #2427299)

Utilizator razviii237Uzum Razvan razviii237 Data 31 mai 2019 15:42:47
Problema Sortare prin comparare Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream f("algsort.in");
ofstream g("algsort.out");

const int maxn = 5e5+5;

int n, i, v[maxn];

void combine(int v[], int st, int dr) {
    int m = (st + dr) / 2;
    int s1 = m - st + 1, s2 = dr - m;
    int *L, *R, k1 = 0, k2 = 0;
    L = new int [s1 + 1]; R = new int [s2 + 1];
    for(i = st; i <= m; i ++) { L[++ k1] = v[i]; }
    for(i = m + 1; i <= dr; i ++) { R[++ k2] = v[i]; }
    k1 = k2 = 1;
    while(k1 <= s1 || k2 <= s2) {
        if(k2 > s2 || (k1 <= s1 && L[k1] < R[k2])) {
            v[st ++] = L[k1 ++];
        } else {
            v[st ++] = R[k2 ++];
        }
    }
}

void mergesort(int v[], int st, int dr) {
    if(st >= dr) { return; }
    int m = (st + dr) / 2;
    mergesort(v, st, m);
    mergesort(v, m + 1, dr);
    combine(v, st , dr);
}

int main()
{
    f >> n;
    for(i = 1; i <= n; i ++) {
        f >> v[i];
    }

    mergesort(v, 1, n);

    for(i = 1; i <= n; i ++) {
        g << v[i] << ' ';
    }g << '\n';

    f.close(); g.close();
    return 0;
}