🚀 go-pugleaf

In article <34666@apple.Apple.COM>, lins@Apple.COM (Chuck Lins) writes:
> Binary Insertion sort and Merge sort are _NOT_ the same thing. They are
> different algorithms. Wirth shows both algorithms in "Algorithms and Data
> Structures". Merge sort requires 2N space (e.g., to sort 1000 element array
> you need a 2000 element array). Binary Insertsion sort is an in-pace sort
> needing only a single temporary.

It is certainly true that Binary Insertion sort and Merge sort are not the
same.  It is seriously misleading to say that Merge sort requires 2N space.
The truth of the matter is that Merge sort requires N (pointers or integers)
*in addition to the data being sorted*, so that if you are sorting records
that contain 100N bytes Merge sort needs 102N bytes total.  Even more to
the point: if you want to sort a *LIST* then the pointer fields Merge sort
needs are already there, and Merge sort doesn't need any more.  (It does
need a stack with O(lg N) pointers, but so does "Quick" sort.)  If you have
N dynamically allocated objects, you are already paying N pointers to refer
to them; if you put those pointers in the objects themselves and link them
into a list, you (a) won't have trouble with fixed-size arrays of pointers
and (b) will be able to use Merge sort with no extra overheads.

Binary Insertion sort does O(N**2) moves, which means that it is seldom a
good idea.  Merge sort costs O(N.lg N) for moves/links as well as comparisons.