Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!mailrus!uwm.edu!gem.mps.ohio-state.edu!ginosko!brutus.cs.uiuc.edu!apple!lins From: lins@Apple.COM (Chuck Lins) Newsgroups: comp.lang.modula2 Subject: Re: Sorts Keywords: Sorting Message-ID: <34666@apple.Apple.COM> Date: 12 Sep 89 16:37:15 GMT References: Organization: Apple Computer Inc, Cupertino, CA Lines: 19 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