/*
	Am avut nevoie de o implementare proprie de sortare la locul meu de munca (Bitdefender)
	si am considerat ca efortul este destul de mare incat sa se merite sa il pun aici
*/

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

int GenericSort(
	size_t Left,
	size_t Right,
	size_t ElementSize,
	void* Array,
	int(*Comparator)(const void*, const void*))
{
	if (Left > Right)
	{
		return 0;
	}

	size_t l = Left;
	size_t r = Right;
	size_t pivot = (Left + Right) / 2;

	void* aux = calloc(1, ElementSize);
	if (NULL == aux)
	{
		return -1;
	}

	char* v = Array;

	do
	{
		while (l < Right && Comparator((const void*)(v + ElementSize*l), (const void*)(v + ElementSize*pivot)) < 0)
		{
			l++;
		}
		while (r > Left && Comparator((const void*)(v + ElementSize*pivot), (const void*)(v + ElementSize*r)) < 0)
		{
			r--;
		}

		if (l < r)
		{
			memcpy(aux, v + ElementSize*l, ElementSize);
			memcpy(v + ElementSize*l, v + ElementSize*r, ElementSize);
			memcpy(v + ElementSize*r, aux, ElementSize);
			if (l < (size_t)-1)
				l++;
			if (r > 0)
				r--;
		}
		else
		{
			break;
		}
	} while (l <= r);

	free(aux);

	if (NULL == Array)
	{
		return -1;
	}

	if (l < Right)
	{
		int retVal = GenericSort(l, Right, ElementSize, Array, Comparator);
		if (retVal != 0)
		{
			return retVal;
		}
	}
	if (r > Left)
	{
		int retVal = GenericSort(Left, r, ElementSize, Array, Comparator);
		if (retVal != 0)
		{
			return retVal;
		}
	}

	return 0;
}


int CompareInts(
	const void* First,
	const void* Second)
{
	int first = *(int*)First;
	int second = *(int*)Second;
	if (first < second)
	{
		return -1;
	}
	if (first > second)
	{
		return 1;
	}
	return 0;
}

int main()
{
	FILE* f = fopen("algsort.in", "r");
	FILE* g = fopen("algsort.out", "w");
	
	int n;
	fscanf(f, "%d", &n);

	int* array = calloc(n, sizeof(int));
	if (NULL == array)
	{
		printf("Memory allocation failed for array.\n");
		return -1;
	}

	for (int i = 0; i < n; i++)
	{
		fscanf(f, "%d", &array[i]);
	}

	int retVal = GenericSort(0, n-1, sizeof(int), array, CompareInts);
	if (0 != retVal)
	{
		fclose(f);
		fclose(g);
		free(array);
		printf("GenericSort failed with end-val 0x%08X\n", retVal);
		return -1;
	}

	for (int i = 0; i < n; i++)
	{
		fprintf(g, "%d ", array[i]);
	}
	
	free(array);

	fclose(f);
	fclose(g);

	return 0;
}