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=