#include <stdio.h>
#include <stdlib.h>

#define swap(a, b, size)                        \
{                                               \
	int __size = (size);                        \
	char *__a = (char*)(a), *__b = (char*)(b);  \
	do{                                         \
		char __tmp = *__a;                      \ 
		*__a = *__b;                            \ 
		*__b = __tmp;                           \
		__a++;                                  \
		__b++;                                  \
	}while(--__size > 0);                       \
}

int cmp(const void *a, const void *b) {
	return *(int *)a - *(int *)b;
}

int read(char *nume_fisier_text, int **v) {
	FILE * fin = fopen(nume_fisier_text, "rt");
	if(fin == NULL) {
		printf("The file can't be opened!\n");
		exit(EXIT_FAILURE);
	}
	
	int i, n;
	fscanf(fin, "%d", &n);
	*v = (int *) malloc(n * sizeof(int));
	if(*v == NULL) {
		printf("Error in allocating memory!\n");
		exit(EXIT_FAILURE);
	}
	
	for(i = 0; i < n; ++i) {
		fscanf(fin, "%d", *v + i);
	}
	
	fclose(fin);
	
	return n;
}

void bubbleSort(void *base, int n, int d, int (*cmp)(const void *, const void *)) {
	char *p = (char*) base;
	int i;
	short ok;
	do {
		ok = 0;
		for(i = 0; i < n - 1; ++i) {
			if(cmp(p + i * d, p + (i + 1) * d) > 0){
				swap(p + i * d, p + (i + 1) * d, d);
				ok = 1;
			}
		}
	}while(ok);
}

void mergeSort(int left, int right, void *base, int d, int (*cmp)(const void *a, const void *b)) {
	if(left < right) {
		int mid = left + ((right - left)/2);
		mergeSort(left, mid, base, d, cmp);
		mergeSort(mid + 1, right, base, d, cmp);
		int i, j, k = 0;
		void *__aux = (void *) malloc((right - left +1) * d);
		if(__aux == NULL) {
			printf("Error in allocating memory!\n");
			free(base);
			exit(EXIT_FAILURE);
		}
		i = left;
		j = mid + 1;
		char *p = (char*) base;
		char *__p = (char*) __aux;
		while(i <= mid && j <= right) {
			if(cmp(p + i * d, p + j * d ) < 0){
				memcpy(__p + k * d, p + i * d, d);
				k++;
				i++;
			}
			else{
				memcpy(__p + k * d, p + j * d, d);
				k++;
				j++;
			}
		}
		
		while(i <= mid ){
			memcpy(__p + k * d, p + i * d, d);
			k++;
			i++;
		}
		while(j <= right){
			memcpy(__p + k * d, p + j * d, d);
			k++;
			j++;
		}
		for(i = left, j = 0; i <= right; ++i, ++j)
			memcpy(p + i * d, __p + j * d, d);
		free(__aux);
	}
}

void display(int n, int *v) {
	FILE * fout = fopen("algsort.out", "wt");
	if(fout == NULL) {
		printf("The file can't be opened!\n");
		exit(EXIT_FAILURE);
	}
	
	int i;
	for(i = 0; i < n; ++i) {
		fprintf(fout, "%d ", v[i]);
	}
	fclose(fout);
}

int main(int argc, char **argv){
	int n, *v = NULL;
	n = read("algsort.in", &v);
	mergeSort(0, n - 1, v, sizeof(int), cmp);
	display(n, v);
	free(v);
	return 0;
}