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: Thu, 01 Sep 2011 05:50:58 -0500
Date: Thu, 01 Sep 2011 03:50:30 -0700
From: Patricia Shanahan <pats@acm.org>
User-Agent: Mozilla/5.0 (Windows NT 5.2; WOW64; rv:6.0) Gecko/20110812 Thunderbird/6.0
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> <gjku571et7noqso1klnuk6n3m932mvh75e@4ax.com>
In-Reply-To: <gjku571et7noqso1klnuk6n3m932mvh75e@4ax.com>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <euSdnVIT3csP_sLTnZ2dnUVZ_hCdnZ2d@earthlink.com>
Lines: 23
X-Usenet-Provider: http://www.giganews.com
NNTP-Posting-Host: 70.230.204.158
X-Trace: sv3-49eT1cFmXlr5EfcwRWgyhgc627FVioTXhh4UoAm3qz+D/jKBOH3SuMGI/XNisBhqfyn+41n9UcAInh0!kZeOJi5BFRDBaFsH6vLv039uGJNBjo090lWyJBoeTFPl08J0TWW9L7ixgXMFrARWA+5g6z+oINl/!D9lG5eSf1SGVhLoSbHn0CBjaPR5++pATliV0MKqqpaUxic0=
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: 2136
Xref: x330-a1.tempe.blueboxinc.net comp.lang.java.programmer:7521

On 9/1/2011 2:38 AM, Roedy Green wrote:
> On Wed, 31 Aug 2011 20:39:09 -0700, markspace<-@.>  wrote, quoted or
> indirectly quoted someone who said :
>
>>
>> Pfft.  No.  Theoretical maximum speed of a sort is something like n
>> log n.  The only data you can sort in n time is data that's already
>> sorted.

The proof of the n log n minimum only applies to comparison sorts.

> see http://mindprod.com/jgloss/radixsort.html
>
> Surely you remember mechanical card sorters. They did precisely
> that.

If I had needed to sort twelve punch cards, I would have done it by
hand, in far less time than it would have taken to walk from my desk to
a mechanical sorter. Fortunately, I never had a desk in same room as a
card sorter. For small problems, overhead time is far more important
than asymptotic behavior.

Patricia