Path: utzoo!utgpu!news-server.csri.toronto.edu!rutgers!usc!sdd.hp.com!decwrl!mejac!orchard.la.locus.com!prodnet.la.locus.com!ITcorp.com From: geoff@ITcorp.com (Geoff Kuenning) Newsgroups: alt.sources Subject: Re: Sorting Algorithm Keywords: Sort Sorting C Source Linked-Lists Message-ID: <15890@oolong.la.locus.com> Date: 21 Aug 90 22:46:34 GMT References: Sender: news@locus.com Reply-To: geoff@ITcorp.com (Geoff Kuenning) Distribution: na Organization: Locus Computing Corporation, Inglewood, CA Lines: 44 In article wayned@wddami.spoami.com (Wayne Diener) writes: > I have been unable to find any references to the sorting algorithm > used in this program. If anyone has seen it elsewhere, I would > appreciate hearing about it. None of my "guru" programmer friends, > my professors (I'm a hardware type who went back to college to learn > a little software) or a literature search have turned up an equivalent Did your professors point out that you are basically just building a binary tree in an expensive fashion? > does the sort "in-place" (requires very little additional memory, > other than a few more variables). I'm not really terribly proficient > at "Big O" analysis, but it LOOKS like it might be O(N*log(N)) > instead of O(N^2). Anyone want to analyse it? Most people would consider list links to be additional memory. As to complexity, it depends tremendously on the cost of comparisons. If comparisons are costly, then the complexity is indeed O(N log N). On the other hand, if comparisons are cheap compared to the cost of following pointers (e.g., you are sorting 32-bit integers), then the complexity becomes at least O(N**2) because you will spend all of your time chasing up and down the list to do your "binary search". (This shows up one of the many deficiencies in "Big O" analysis). > The sorting is accomplished using a binary search of a linked list > to find the the proper insertion point (just running up and down > the pointers and dividing the list in half each time) and then > moving the pointers to change an item's location. This is very similar to building a binary tree, or possibly a balanced binary tree. Binary tree insertion is O(N log N); I think balanced trees have similar complexity but I don't have a reference handy to verify this at the moment. The way your code does the binary search is potentially very expensive compared to the cost of keeping the tree balanced, especially with very large data bases. Having said all the above, let me add that I do think your algorithm is interesting, and it was thoughtful of you to post it. In some situations, your algorithm will be the superior choice, and it may also inspire some interesting derivatives. Geoff Kuenning geoff@la.locus.com geoff@ITcorp.com