Dropping from quadratic to linear complexity

complexity.c

/*
In computer science, algorithmic complexity is represented by something called
Big-Oh notation. Writing O(1) means a function will take the same amount of 
time no matter how large the input is, ie: it is constant. O(n) means it will 
take linear time, for example if you double the amount of input, the time taken
to perform that function will also double. Other common complexities are O(n^2),
O(log(n)), and O(n log(n)). Note, in most cases the logarithm is log base 2.

The following functions basically split a list of numbers in the following way:
{0, 1, 2, 3, 4, 5, 6, 7}
into
{0, 2, 4, 6, 1, 3, 5, 7}
It takes values at odd indices (in this example represented by odd numbers),
and places them in the upper half of the array. Even indexed values are 
consequently moved to the beginning half. At then end, they are also ordered in
the initial ordering, except split by the even/oddness of their index.

This was the initial function:
*/
void split(double *vals, int length){
	int start = 1;
	int end = length-1;

	while (start < end) {
		int i;
		double tmp;
		for (i = start; i < end; i = i + 2) {
			tmp = vals[i];
			vals[i] = vals[i+1];
			vals[i+1] = tmp;
		}
		start = start + 1;
		end = end - 1;
	}
}
/*
It runs in O(n^2) time. For example, with a data set that had a length 
of 2^16, it took around 3.39 seconds to apply the function.

I replaced it with this:
*/
void split(double *vals, int length){
	int half = length / 2;
	// Split even and odd
	for(int i = 0; i < (half / 2); ++i){
		int even = i * 2;
		int odd = even + 1;
		double t = vals[odd];
		vals[odd] = vals[half + even];
		vals[half + even] = t;
	}
	// Now recurse on each half
	if(half >= 4){
		liftSplit(vals, half);
		liftSplit(vals + half, half);
	}
}
/*
Basically, it gets halfway to the right answer, then does the same set 
of operations on each half of the list, and so on and so on. The complexity 
for this function is O(n), which is much better. This version of the 
function takes 0.004 seconds to do the same work as the previous function. 
In roughly the same time it takes the old version to operate on 2^15 elements, 
the new version can do the same work on 2^25 elements. Thats over 1000x more
productive (1024x to be precise).


TL;DR: I rewrote a chunk of code that is literally 1000x times better than 
an older version.
*/