module sort;

private import std.c.stdlib;

template TSort(T)
{
	/*void mergeSort(T[] array)
	{
		if (array.length <= 1)
			return;

		int mid = array.length / 2;

		mergeSort(array[0..mid]);
		mergeSort(array[mid..$]);

		merge(array, mid);
	}*/

	void mergeSort(T[] array, int delegate(T a, T b) cmp)
	{
		if (array.length <= 1)
			return;

		int mid = array.length / 2;

		mergeSort(array[0..mid], cmp);
		mergeSort(array[mid..$], cmp);

		merge(array, mid, cmp);
	}
	
	private void merge(T[] array, int mid)
	{
		static const int STACKALLOC_TRESHOLD = 1024;
		
		int i = 0;
		int j = mid;
		int k = 0;
		int end = array.length;
		T[] temp = null;
		
		if (end < STACKALLOC_TRESHOLD)
		{
			uint size = end * T.sizeof;
			temp = cast(T[])alloca(size)[0..size];
			debug printf("Array length %d, using stack allocation\n", end);
		}
		else
		{
			temp = new T[end];
			debug printf("Array length %d, using heap allocation\n", end);
		}
		
		while ((i < mid) && (j < end))
		{
			if (array[i] <= array[j])
				temp[k++] = array[i++];
			else 
				temp[k++] = array[j++];
		}
		
		while (i < mid)
		temp[k++] = array[i++];
		
		while (j < end)
			temp[k++] = array[j++];
		
		for (i = 0; i < end; i++)
			array[i] = temp[i];
	}
	
	private void merge(T[] array, int mid, int delegate(T a, T b) cmp)
	{
		static const int STACKALLOC_TRESHOLD = 1024;
		
		int i = 0;
		int j = mid;
		int k = 0;
		int end = array.length;
		T[] temp = null;
		
		if (end < STACKALLOC_TRESHOLD)
		{
			uint size = end * T.sizeof;
			temp = cast(T[])alloca(size)[0..size];
			debug printf("Array length %d, using stack allocation\n", end);
		}
		else
		{
			temp = new T[end];
			debug printf("Array length %d, using heap allocation\n", end);
		}
		
		while ((i < mid) && (j < end))
		{
			int ord = cmp(array[i], array[j]);
			if (ord == -1 || ord == 0)
				temp[k++] = array[i++];
			else 
				temp[k++] = array[j++];
		}
		
		while (i < mid)
		temp[k++] = array[i++];
		
		while (j < end)
			temp[k++] = array[j++];
		
		for (i = 0; i < end; i++)
			array[i] = temp[i];
	}
}

interface SomeInterface
{
}

class SomeClass : SomeInterface
{
}

void main()
{
	SomeClass c = new SomeClass();
	SomeInterface[] arr = new SomeInterface[1];
	arr[0] = c;
	TSort!(SomeInterface).mergeSort(arr, null);
}