• David Medlock (13/13) Jan 14 2006 Here is an inplace version of a natural mergesort.

David Medlock <noone nowhere.com> writes:

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


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