Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!news.albasani.net!.POSTED!not-for-mail
From: Lew <noone@lewscanon.com>
Newsgroups: comp.lang.java.programmer
Subject: Re: Did the sort do anything?
Date: Sat, 14 May 2011 23:24:06 -0400
Organization: albasani.net
Lines: 22
Message-ID: <iqnh0d$m0m$1@news.albasani.net>
References: <eskis656eeu0of5f5do1ogdpfbdau3d06i@4ax.com> <iqbmo6$j47$1@dont-email.me> <iqkt5k$k58$1@lust.ihug.co.nz>
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
X-Trace: news.albasani.net cuTrsR6u8lYTE6P2L5xtpueFHYWc/veTMGVR6vI5YusMQWj1ODF1eehPArox60jXxjSLAvJ38wUD9W/aBQlcGlgElOfLg3Ryepz3MS/tQh9M47CE4R+hcvdPS7yA6Wb+
NNTP-Posting-Date: Sun, 15 May 2011 03:23:57 +0000 (UTC)
Injection-Info: news.albasani.net; logging-data="G40lUQP8fb/ZTS4sUz25S4BtDekVLest+22J3Tfl1stEiNlsQL5u8x27wNSYfdEtBg56UM/yKs+XmLteXJva6CjbdR8g97rNOiCCP+4MCGKpc+er5p1QqjcUEyAQuVFD"; mail-complaints-to="abuse@albasani.net"
User-Agent: Mozilla/5.0 (X11; U; Linux x86_64; en-US; rv:1.9.2.17) Gecko/20110424 Thunderbird/3.1.10
In-Reply-To: <iqkt5k$k58$1@lust.ihug.co.nz>
Cancel-Lock: sha1:fkyNSel/PJCAqTwBDcFfAwV1V7Y=
Xref: x330-a1.tempe.blueboxinc.net comp.lang.java.programmer:4100

Lawrence D'Oliveiro wrote:
> In message<iqbmo6$j47$1@dont-email.me>,  wrote:
>
>> ...  a Tim sort (soon to be the standard sort in Java) ...
>
> Gee, I wonder what language that came from ...

Tim Peters wrote it in C.
http://svn.python.org/projects/python/trunk/Objects/listobject.c

And the algorithm itself came from neither C nor any other computer language; 
it came from English.

<http://www.kiwidoc.com/java/l/x/android/android/5/p/java.util/c/TimSort>
"The underlying techniques are described in this paper (and may have even 
earlier origins): "Optimistic Sorting and Information Theoretic Complexity" 
Peter McIlroy SODA (Fourth Annual ACM-SIAM Symposium on Discrete Algorithms), 
pp 467-474, Austin, Texas, 25-27 January 1993."

-- 
Lew
Plppptththpthpphtpthhph!