digitalmars.D - in place merge sort
- David Medlock (13/13) Jan 14 2006 Here is an inplace version of a natural mergesort.
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
Jan 14 2006