// The Half-sort algorithm is distributed under the terms
// of the GNU General Public License. So basically anyone
// is allowed to use or re-engineer this code freely.

Below is some pseudo-code that may help you to
understand how the algorithm works. You can
also read through the actual C++ code because
I have put many comments.

Here, in very basic terms, is what the Half-sort
algorithm does:

BEGIN ALGORITHM

1	Assign an integer called Mid with a
	number that is half way between the
	smallest number in the array and the biggest.

2	Look from the start of the array forwards
	until a number bigger than Mid has been found.

3	Look from the end of the array backwards
	until a number smaller than Mid is found.

4	Swap those two numbers in the array around.

5	Carry on doing this until the two places you
	are looking at have met (they are the same place).
	You are now looking at the middle of array,
	at least in terms of high and low numbers.

6	Now repeat these steps on each side of
	array, until it is fully sorted.

END ALGORITHM

That is all there is to it. Simple huh!
