Cod sursa(job #2897344)

Utilizator anne_marieMessner Anne anne_marie Data 3 mai 2022 15:10:09
Problema Sortare prin comparare Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.37 kb
#include <fstream>
using namespace std;
ifstream fin("algsort.in");
ofstream fout("algsort.out");



void merge(int v[], int l, int mid, int r) {
    auto const lung1 = mid - l + 1;
    auto const lung2 = r - mid;

    auto *v1 = new int[lung1], *v2 = new int[lung2];
    for (int i = 0; i < lung1; i++) {
        v1[i] = v[l + i];
    }
    for (int i = 0; i < lung2; i++) {
        v2[i] = v[mid + 1 + i];
    }
    int index1 = 0, index2 = 0, indexMerged = l;
    while (index1 < lung1 && index2 < lung2) {
        if(v1[index1]  <= v2[index2]){
            v[indexMerged] = v1[index1];
            index1 ++;
        } else {
            v[indexMerged] = v2[index2];
            index2 ++;
        }
        indexMerged ++;
    }
    while(index1 < lung1){
        v[indexMerged] = v1[index1];
        index1 ++;
        indexMerged ++;
    }
    while(index2 < lung2){
        v[indexMerged] = v2[index2];
        index2 ++;
        indexMerged ++;
    }
}

void mergeSort(int v[], int l, int r){
    if (l >= r)
        return;
    int mid = l + (r - l)/2;
    mergeSort(v, l, mid);
    mergeSort(v, mid + 1, r);
    merge(v, l, mid, r);

}

void printV(int v[], int n) {
    for(int i = 0; i < n; i ++){
        fout << v[i] << " ";
    }
}

int main() {
    int n;
    int v[500002];
    fin >> n;
    for(int i = 0; i < n; i ++)
        fin >> v[i];
    mergeSort(v, 0, n - 1);
    printV(v, n);
}