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

Re: Using Java Classes to Sort a Small Array Quickly

Date	2011-09-16 23:14 -0700
From	Patricia Shanahan <pats@acm.org>
Newsgroups	comp.lang.java.programmer
Subject	Re: Using Java Classes to Sort a Small Array Quickly
References	(5 earlier) <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>
Message-ID	<baSdnU7u2r5Bp-nTnZ2dnUVZ_uqdnZ2d@earthlink.com> (permalink)

Show all headers | 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