🚀 go-pugleaf

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.

HeapSort is a good algorithm that guarantees sorting in O(n log n) time
regardless of the input. Though, "most" of the time Quicksort will outperform
it. Quicksort's main problem is that is has a worst-case asymptotic complexity
of O(n**2) which typically occurs when the array is already sorted in either
ascending or descending sequence. Optimizations can reduce the chances of poor
performance in the worst case but cannot eliminate it.


-- 
Chuck Lins                      | "Exit right to funway."
Internet:   lins@apple.com      | AppleLink: LINS
Snail Mail: 20525 Mariani Ave. M/S: 41-K Cupertino, CA 95014
"I like the future - I'm in it." - Firesign Theater