double CalculateMedianRecursive(double *inputList, int inputListLength, int lessThanSum, int greaterThanSum, bool evenTotal)
{
	double *lessThanMedian, *greaterThanMedian;
	lessThanMedian = ( double* ) alloca( inputListLength * sizeof(double) );
	greaterThanMedian = ( double* ) alloca( inputListLength * sizeof(double) );

	int lessThanMedianListLength=0, greaterThanMedianListLength=0;
	double median=inputList[0];
	int i;
	for (i=1; i < inputListLength; i++)
	{
		// If same value, spread among lists evenly
		if (inputList[i]<median || ((i&1)==0 && inputList[i]==median))
			lessThanMedian[lessThanMedianListLength++]=inputList[i];
		else
			greaterThanMedian[greaterThanMedianListLength++]=inputList[i];
	}

	if (evenTotal)
	{
		if (lessThanMedianListLength+lessThanSum==greaterThanMedianListLength+greaterThanSum+1 ||
			lessThanMedianListLength+lessThanSum==greaterThanMedianListLength+greaterThanSum-1)
			return median;
	}
	else
	{
		if (lessThanMedianListLength+lessThanSum==greaterThanMedianListLength+greaterThanSum)
			return median;
	}

	if (lessThanMedianListLength+lessThanSum < greaterThanMedianListLength+greaterThanSum)
	{
		lessThanMedian[lessThanMedianListLength++]=median;
		return CalculateMedianRecursive(greaterThanMedian, greaterThanMedianListLength, lessThanMedianListLength+lessThanSum, greaterThanSum, evenTotal);
	}
	else
	{
		greaterThanMedian[greaterThanMedianListLength++]=median;
		return CalculateMedianRecursive(lessThanMedian, lessThanMedianListLength, lessThanSum, greaterThanMedianListLength+greaterThanSum, evenTotal);		
	}
}

double FindMedian(double *inputList, int inputListLength)
{
	return CalculateMedianRecursive(inputList, inputListLength, 0, 0, inputListLength % 2 == 0);
}