Path: csiph.com!x330-a1.tempe.blueboxinc.net!newsfeed.hal-mli.net!feeder1.hal-mli.net!border3.nntp.dca.giganews.com!Xl.tags.giganews.com!border1.nntp.dca.giganews.com!nntp.giganews.com!local2.nntp.dca.giganews.com!nntp.earthlink.com!news.earthlink.com.POSTED!not-for-mail NNTP-Posting-Date: Sat, 17 Sep 2011 01:14:52 -0500 Date: Fri, 16 Sep 2011 23:14:48 -0700 From: Patricia Shanahan User-Agent: Mozilla/5.0 (Windows NT 5.2; WOW64; rv:6.0.2) Gecko/20110902 Thunderbird/6.0.2 MIME-Version: 1.0 Newsgroups: comp.lang.java.programmer Subject: Re: Using Java Classes to Sort a Small Array Quickly References: <86c4a53b-1ca1-48a8-b954-c01bd449278a@s35g2000prm.googlegroups.com> <4e6d5bf5$0$316$14726298@news.sunsite.dk> <4e6e9217$0$308$14726298@news.sunsite.dk> <900ffdda-7170-44e3-a141-bfec09c74dd1@glegroupsg2000goo.googlegroups.com> In-Reply-To: Content-Type: text/plain; charset=ISO-8859-15; format=flowed Content-Transfer-Encoding: 7bit Message-ID: Lines: 14 X-Usenet-Provider: http://www.giganews.com NNTP-Posting-Host: 70.230.204.200 X-Trace: sv3-V62MJsaVXIyts9rBr7ngUe45MxYvMVvbB8Uc6CDMaRUd7sD2ht5+gnpLdAe9r4sMGcwxU9Ckb6DlDRZ!JDIXiB3KhfpnWXuROs38HlH/ZD5PDohs5eirbCQRkBoI5RlV+n7TMWrTaPqoCCOj4MG40KrSqAnD!cZOHZFxyIxdiOLEpVE96sI9zxpgaC/FSPvWtQjTKJ7rP3fE= X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly X-Postfilter: 1.3.40 X-Original-Bytes: 2150 Xref: x330-a1.tempe.blueboxinc.net comp.lang.java.programmer:8101 On 9/16/2011 5:54 PM, Wanja Gayk wrote: ... > The claim was that _any_ sort would be at least O(n log n). I've proven > him wrong by sorting something in o(n) using a kind of bucket sort, that > trades number range for runtime complexity. ... Why not just go with radix sort? It seems like a better example of a practical O(n) sort. The proof of the \Omega(n log n) lower bound only applies to comparison sorts, so there is nothing surprising about the existence of O(n) sorts. Patricia