Groups > comp.lang.java.programmer > #8101

Re: Using Java Classes to Sort a Small Array Quickly

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 <pats@acm.org>
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> <j3mupc$d5m$1@dont-email.me> <MPG.28d742f5c91d21e9896b8@202.177.16.121> <j4jala$dkh$1@dont-email.me> <MPG.28d76557830521d69896ba@202.177.16.121> <4e6d5bf5$0$316$14726298@news.sunsite.dk> <d3d945e5-5d2c-4d95-9f65-31bd73f1f186@glegroupsg2000goo.googlegroups.com> <4e6e9217$0$308$14726298@news.sunsite.dk> <900ffdda-7170-44e3-a141-bfec09c74dd1@glegroupsg2000goo.googlegroups.com> <MPG.28de0ddeec8a3b19896bd@202.177.16.121>
In-Reply-To	<MPG.28de0ddeec8a3b19896bd@202.177.16.121>
Content-Type	text/plain; charset=ISO-8859-15; format=flowed
Content-Transfer-Encoding	7bit
Message-ID	<baSdnU7u2r5Bp-nTnZ2dnUVZ_uqdnZ2d@earthlink.com> (permalink)
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

Show key headers only | View raw

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

Back to comp.lang.java.programmer | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Re: Using Java Classes to Sort a Small Array Quickly Wanja Gayk <brixomatic@yahoo.com> - 2011-09-11 23:14 +0200
  Re: Using Java Classes to Sort a Small Array Quickly Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-09-11 17:53 -0400
    Re: Using Java Classes to Sort a Small Array Quickly Wanja Gayk <brixomatic@yahoo.com> - 2011-09-12 01:40 +0200
      Re: Using Java Classes to Sort a Small Array Quickly Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-09-11 20:32 -0400
        Re: Using Java Classes to Sort a Small Array Quickly Wanja Gayk <brixomatic@yahoo.com> - 2011-09-17 02:54 +0200
          Re: Using Java Classes to Sort a Small Array Quickly Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-09-16 21:03 -0400
            Re: Using Java Classes to Sort a Small Array Quickly Wanja Gayk <brixomatic@yahoo.com> - 2011-09-17 16:52 +0200
              Re: Using Java Classes to Sort a Small Array Quickly Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-09-17 11:05 -0400
                Re: Using Java Classes to Sort a Small Array Quickly Wanja Gayk <brixomatic@yahoo.com> - 2011-09-18 15:41 +0200
                Re: Using Java Classes to Sort a Small Array Quickly Lew <lewbloch@gmail.com> - 2011-09-18 12:53 -0700
                Re: Using Java Classes to Sort a Small Array Quickly Patricia Shanahan <pats@acm.org> - 2011-09-18 13:20 -0700
      Re: Using Java Classes to Sort a Small Array Quickly Arne Vajhøj <arne@vajhoej.dk> - 2011-09-11 21:10 -0400
        Re: Using Java Classes to Sort a Small Array Quickly Lew <lewbloch@gmail.com> - 2011-09-11 20:30 -0700
          Re: Using Java Classes to Sort a Small Array Quickly Arne Vajhøj <arne@vajhoej.dk> - 2011-09-12 19:13 -0400
            Re: Using Java Classes to Sort a Small Array Quickly Lew <lewbloch@gmail.com> - 2011-09-12 17:42 -0700
              Re: Using Java Classes to Sort a Small Array Quickly Wanja Gayk <brixomatic@yahoo.com> - 2011-09-17 02:54 +0200
                Re: Using Java Classes to Sort a Small Array Quickly Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-09-16 21:13 -0400
                Re: Using Java Classes to Sort a Small Array Quickly Patricia Shanahan <pats@acm.org> - 2011-09-16 23:14 -0700
                Re: Using Java Classes to Sort a Small Array Quickly Wanja Gayk <brixomatic@yahoo.com> - 2011-09-17 16:53 +0200
            Re: Using Java Classes to Sort a Small Array Quickly Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-09-12 21:24 -0400
      Re: Using Java Classes to Sort a Small Array Quickly Gene Wirchenko <genew@ocis.net> - 2011-09-12 10:57 -0700
        Re: Using Java Classes to Sort a Small Array Quickly Arne Vajhøj <arne@vajhoej.dk> - 2011-09-12 19:01 -0400
          Re: Using Java Classes to Sort a Small Array Quickly Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-09-12 21:29 -0400
            Re: Using Java Classes to Sort a Small Array Quickly markspace <-@.> - 2011-09-12 19:49 -0700
              Re: Using Java Classes to Sort a Small Array Quickly Lew <lewbloch@gmail.com> - 2011-09-12 21:51 -0700
              Re: Using Java Classes to Sort a Small Array Quickly Joshua Cranmer <Pidgeot18@verizon.invalid> - 2011-09-13 11:32 -0500
              Re: Using Java Classes to Sort a Small Array Quickly Arne Vajhøj <arne@vajhoej.dk> - 2011-09-13 21:51 -0400
                Re: Using Java Classes to Sort a Small Array Quickly Gene Wirchenko <genew@ocis.net> - 2011-09-14 11:00 -0700
            Re: Using Java Classes to Sort a Small Array Quickly Patricia Shanahan <pats@acm.org> - 2011-09-13 06:33 -0700
          Re: Using Java Classes to Sort a Small Array Quickly Gene Wirchenko <genew@ocis.net> - 2011-09-13 09:48 -0700

csiph-web