From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,385be4c68a9e4de6 X-Google-Attributes: gid103376,public X-Google-ArrivalTime: 2002-07-08 10:36:42 PST Path: archiver1.google.com!news1.google.com!newsfeed.stanford.edu!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!newsfeed1.cidera.com!Cidera!cyclone.socal.rr.com!cyclone3.kc.rr.com!news3.kc.rr.com!twister.socal.rr.com.POSTED!not-for-mail From: "Ron" Newsgroups: comp.lang.ada References: <3D21D581.6EF6CB06@despammed.com> <3D21DC25.AD402F70@easystreet.com> <3D220648.6F3BE45D@despammed.com> <3D2221CD.3F619935@easystreet.com> Subject: Re: Smart sorting algorithm ? X-Priority: 3 X-MSMail-Priority: Normal X-Newsreader: Microsoft Outlook Express 5.50.4807.1700 X-MimeOLE: Produced By Microsoft MimeOLE V5.50.4807.1700 Message-ID: Date: Mon, 08 Jul 2002 17:36:42 GMT NNTP-Posting-Host: 24.30.156.163 X-Complaints-To: abuse@rr.com X-Trace: twister.socal.rr.com 1026149802 24.30.156.163 (Mon, 08 Jul 2002 10:36:42 PDT) NNTP-Posting-Date: Mon, 08 Jul 2002 10:36:42 PDT Organization: RoadRunner - West Xref: archiver1.google.com comp.lang.ada:26943 Date: 2002-07-08T17:36:42+00:00 List-Id: First, I hope Wes has investigated non-comparison-based sorting... Second, Wes never indicated the number of items to sort, but used small values (18 and 36) as examples. If you only want to sort a small number of items, then the On-Line Encyclopedia of Integer Sequences (http://www.research.att.com/~njas/sequences/index.html) may be of help: To sort 18 items (referenced by sequence number): A036604 lists the minimal number of comparisons needed to sort n elements, but only goes up to n=12. A003070 gives 53 for ceiling(log_2 n!) (the lower bound on number of comparisons required for comparison-based sorting) A001768 gives 54 comparisons for merge sort A001855 gives 59 comparisons for sorting by binary insertion A003071 gives 67 comparisons for sorting by list merging A006282 gives 82 comparisons for Batcher's parallel sort (which can be implemented via a sorting network) Also, the best sorting network I'm aware of requires 79 comparison-exchanges. Third, quicksort isn't very good for a small number of items because of its worst-case performance and overhead, which is why most sorting algorithms based upon quicksort us another sorting method once the sub-lists are small. Good luck! - Ron Zeno