#strict 2

global func SortNumeric(int a, int b)
{
	if(a < b)
	{
		return -1;
	}
	else if(a > b)
	{
		return 1;
	}
}

global func SortNumericInverse(int a, int b)
{
	return -SortNumeric(a, b);
}

global func QSort(array& data, callback, callbackArgs) // WARNING: Can cause stack-overflow with too much data
{
	if(callback == true)
	{
		callback = GlobalCallback("SortNumericInverse");
	}
	QSort_Part(data, callback || GlobalCallback("SortNumeric"), 0, GetLength(data) - 1, callbackArgs);
	return data;
}

global func QSort_Part(array& data, callback, int left, int right, callbackArgs)
{
	if(left < right)
	{
		// Partitioning
		var pPos = RandomX(left, right);
		var p = data[pPos];
		var tmp;

		tmp = data[pPos];
		data[pPos] = data[right];
		data[right] = tmp;
		pPos = right;

		var i = left - 1;
		for(var j = left; j <= right; ++j)
		{
			if(Call(callback, data[j],  p, callbackArgs) < 0)
			{
				++i;
				tmp = data[i];
				data[i] = data[j];
				data[j] = tmp;
			}
		}

		++i;

		tmp = data[i];
		data[i] = data[pPos];
		data[pPos] = tmp;
		// -----

		QSort_Part(data, callback, left, i - 1, callbackArgs);
		QSort_Part(data, callback, i + 1, right, callbackArgs);
	}
}