Here is an inplace version of a natural mergesort.

For those who don't know the basic algorithm is:
1. Find the first sorted sublist in the array
2. If the first list == array length, stop
2. Find the next sorted sublist in the array
3. Merge the two sublists, assign it as the first list
4. Goto #2

I actually wrote this for the discussion page on merge sort on wikipedia.  I attached the python version for comparison.

I don't use slices because slices make new lists in python, and I wanted inplace sorting.

Its not templated yet, and its in the public domain.
-David M