• David Medlock <noone nowhere.com> Jan 14 2006

David Medlock <noone nowhere.com> writes:

Content-Type: text/plain; charset=us-ascii; format=flowed
Content-Transfer-Encoding: 7bit

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