Cod sursa(job #2151265)

Utilizator tudoroprisTudor Opris tudoropris Data 4 martie 2018 12:08:07
Problema Sortare prin comparare Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <fstream>

const int MaxN = 500005;

using namespace std;

ifstream cin("algsort.in");
ofstream cout("algsort.out");

int v[MaxN], g[MaxN];

void MergeVect(int l, int r) {
	int m = (l + r) / 2, p = l, q, gnr=l;
	q = m + 1;
	while (p <= m && q <= r) {
		if (v[p] < v[q]) {
			g[gnr] = v[p];
			p++;
		}
		else {
			g[gnr] = v[q];
			q++;
		}
		gnr++;
	}
	for (; p <= m; ++p) {
		g[gnr] = v[p];
		gnr++;
	}
	for (; q <= r; q++) {
		g[gnr] = v[q];
		gnr++;
	}
	for (gnr = l; gnr <= r; gnr++) {
		v[gnr] = g[gnr];
	}
}

void Merge(int l, int r) {
	if (l == r) {
		return;
	}
	int m = (l + r) / 2;
	Merge(l, m);
	Merge(m + 1, r);
	MergeVect(l, r);
}

int main(){
	int n;
		cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> v[i];
	Merge(1, n);
	for (int i = 1; i <= n; i++)
		cout << v[i] << ' ';
    return 0;
}