Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!batcomputer!munnari.oz.au!goanna!ok From: ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) Newsgroups: comp.lang.scheme Subject: Re: Tail recursion - it's not just for breakfast any more. Message-ID: <5815@goanna.cs.rmit.oz.au> Date: 18 May 91 09:08:26 GMT References: <1991May14.134257.16696@newcastle.ac.uk> Distribution: comp Organization: Comp Sci, RMIT, Melbourne, Australia Lines: 14 In article <1991May14.134257.16696@newcastle.ac.uk>, Chris.Holt@newcastle.ac.uk (Chris Holt) writes: > Aren't tail-recursive sorts bounded by o(n**2), while doubly-recursive > sorts bounded by o(n*log n)? If you are willing to use an explicit stack to hold runs, a bottom-up implementation of "natural" merge sort (see Knuth for what "natural" means here) can be coded tail-recursively. The code is pretty short, too. With a slight generalisation of the idea of a run (which I tried to publish in IPL some years ago, without success), a tail recursive merge sort can sort already ascending or already descending sequences in O(n), and has worst case ~ n.lg n. -- There is no such thing as a balanced ecology; ecosystems are chaotic.