Thursday, 11 October 2012


Half-sort is a sorting algorithm. A copy of it can be found here:

It has the following features:

  • It is an in-place sort. (No extra data space needed.)
  • It works by "divide and conquer" recursion. (It is quite like Quick-sort and Merge-sort.)
  • It is not stable. (i.e. It does NOT keep the original order of identically valued items in the list.)

Here is some pseudo-code that explains how the Half-sort algorithm works:

  1. Calculate M to be a value that is half way between the smallest item and the biggest item in the collection. You may have to scan the entire collection to find this value, but it may already be known or can be easily calculated.
  2. L begins by pointing to the start of the collection and moves forwards until an item bigger than M has been found.
  3. R begins by pointing to the end of the collection and moves backwards until an item smaller than M is found.
  4. Swap the items at L and R.
  5. Carry on doing this until L and R meet in the middle. This would be the mean average middle, not the middle index position.
  6. Now repeat these steps on each side of collection, until it is fully sorted.

This code is completely free to use by anybody. It is held under the Do What You Want To Public License:

No comments:

Post a Comment