Cod sursa(job #1526053)

Utilizator FayedStratulat Alexandru Fayed Data 15 noiembrie 2015 21:19:01
Problema Sortare prin comparare Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.15 kb
#include <stdio.h>
#include <stdlib.h>
#define NMAX 500001

int V[NMAX];
int N;

void reads() {
    
    freopen("algsort.in",  "r", stdin);
    freopen("algsort.out", "w", stdout);
    
    scanf("%d", &N);
    
    for(int i = 1; i <= N; ++i)
        scanf("%d", &V[i]);
}

void merge(int left, int m, int right) {
    
    int leftHalf  = left;
    int rightHalf = m + 1;
    
    int temp[NMAX];
    int len = 0;
    
    while(leftHalf <= m && rightHalf <= right)
        if(V[leftHalf] <= V[rightHalf])
            temp[++len] = V[leftHalf++];
        else
            temp[++len] = V[rightHalf++];
    
    while(leftHalf <= m)
        temp[++len] = V[leftHalf++];
    
    while(rightHalf <= right)
        temp[++len] = V[rightHalf++];
    
    for(int i = left; i <= right; ++i)
        V[i] = temp[i - left + 1];
}

void merge_sort(int left, int right) {
    
    if(left < right) {
        int m = (left + right) / 2;
        merge_sort(left, m);
        merge_sort(m + 1, right);
        merge(left, m, right);
    }
}

int main(void) {
    
    reads();
    merge_sort(1, N);
    
    for(int i = 1; i <= N; ++i)
        printf("%d ", V[i]);
    
    return 0;
}