Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!cs.utexas.edu!sun-barr!apple!ames!uhccux!munnari.oz.au!cs.mu.oz.au!ok From: ok@cs.mu.oz.au (Richard O'Keefe) Newsgroups: comp.lang.modula2 Subject: Re: Sorts Summary: space requirements of merge sort Keywords: Sorting Message-ID: <2093@munnari.oz.au> Date: 13 Sep 89 05:32:10 GMT References: <34666@apple.Apple.COM> Sender: news@cs.mu.oz.au Lines: 22 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.