[net.lang] Merge Sort

ech@spuxll.UUCP (06/15/84)

Yes, a merge sort is *always* O(n log n).  However, one has to go to
heroic measures to do a merge that is both O(n) time and *in-place*.

Quicksort, bubble sort, and others of that ilk are in-place and USUALLY
O(n log n); heapsort is ALWAYS O(n log n) but has (at least according
to Knuth) a higher proportionality constant.

An in-place linear merge is possible, but also has an impossible constant:
there is one by Kronrod, recounted in the exercises of Knuth v. 3 (I don't
remember exactly -- check the index for Kronrod).

If there is any more interest in this particular dead end :-) let me
know.  I have a particularly nifty O(n log n) merge (results in a
O(n (log n)^2) sort) which is in-place and has some other neat properties.
think of it as a puzzle, and yes it is a divide-and-conquer algorithm...

=Ned=