Cod sursa(job #2898318)

Utilizator Mike07Mihai-Alexandru Militaru Mike07 Data 6 mai 2022 16:31:27
Problema Sortare prin comparare Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.22 kb
#include <bits/stdc++.h>
using namespace std;
int n, v[500001];

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


void merge(int v[], int l, int mid, int r){
    int lung1 = mid - l + 1;
    int lung2 = r - mid;
    int v1[lung1], v2[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;
    int index2=0;
    int index3=l;
    while (index1 < lung1 && index2 < lung2) {
        if(v1[index1]  <= v2[index2]){
            v[index3] = v1[index1];
            index1 ++;
        } else {
            v[index3] = v2[index2];
            index2 ++;
        }
        index3 ++;
    }
    while(index1<lung1){
        v[index3]=v1[index1];
        index1++;
        index3++;
    }

    while(index2<lung2){
        v[index3]=v2[index2];
        index2++;
        index3++;
    }
}


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


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

    mergeSort(v,0,n-1);
    for(int i=0;i<n;i++){
        g<<v[i]<<" ";
    }

    return 0;
}