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

Re: Did the sort do anything?

From	Tom Anderson <twic@urchin.earth.li>
Newsgroups	comp.lang.java.programmer
Subject	Re: Did the sort do anything?
Date	2011-05-15 15:12 +0100
Organization	Stack Usenet News Service
Message-ID	<alpine.DEB.2.00.1105151510490.12373@urchin.earth.li> (permalink)
References	(1 earlier) <iqbmo6$j47$1@dont-email.me> <iqkt5k$k58$1@lust.ihug.co.nz> <iqnh0d$m0m$1@news.albasani.net> <alpine.DEB.2.00.1105151117070.12373@urchin.earth.li> <iqof19$rkb$1@dont-email.me>

Show all headers | View raw

On Sun, 15 May 2011, markspace wrote:

> On 5/15/2011 3:20 AM, Tom Anderson wrote:
>
>> What would shut me up would be a performance comparison of two 
>> comparable-quality implementations of the algorithms, showing that 
>> Timsort wipes the floor with Smoothsort. Is anyone aware of one?
>
> I'm not sure, but I believe the advantage of Timsort over Smoothsort is 
> that Timsort has O(n) performance for both ascending and descending 
> sequences, where Smoothsort appears to only have O(n) for ascending 
> sequences.

Interesting point. You could probably get round that by having Smoothsort 
make an initial guess at the direction of the sequence, and then sort 
backwards (forwards but with an inverted comparison) if appropriate, but 
that's the first step down the path of hackery which Timsort has already 
so victoriously travelled.

> There was a recent "shoot out" among various sort algorithms, and 
> Timsort won.  I don't recall exactly which algorithms were included, but 
> I'm sure if Smoothsort were a serious contender it would have been 
> examined.

I'd be very interested to see that shootout - do you remember where it 
was?

tom

-- 
a moratorium on the future

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

Thread

Did the sort do anything? Roedy Green <see_website@mindprod.com.invalid> - 2011-05-10 08:06 -0700
  Re: Did the sort do anything? markspace <-@.> - 2011-05-10 08:48 -0700
    Re: Did the sort do anything? Lawrence D'Oliveiro <ldo@geek-central.gen.new_zealand> - 2011-05-14 15:33 +1200
      Re: Did the sort do anything? Lew <noone@lewscanon.com> - 2011-05-14 08:56 -0400
        Re: Did the sort do anything? Andreas Leitgeb <avl@gamma.logic.tuwien.ac.at> - 2011-05-14 13:54 +0000
          Re: Did the sort do anything? Lawrence D'Oliveiro <ldo@geek-central.gen.new_zealand> - 2011-05-15 11:16 +1200
      Re: Did the sort do anything? Lew <noone@lewscanon.com> - 2011-05-14 23:24 -0400
        Re: Did the sort do anything? Tom Anderson <twic@urchin.earth.li> - 2011-05-15 11:20 +0100
          Re: Did the sort do anything? Lew <noone@lewscanon.com> - 2011-05-15 07:00 -0400
            Re: Did the sort do anything? Tom Anderson <twic@urchin.earth.li> - 2011-05-15 15:09 +0100
              Re: Did the sort do anything? Lawrence D'Oliveiro <ldo@geek-central.gen.new_zealand> - 2011-05-16 14:28 +1200
                Re: Did the sort do anything? Joshua Cranmer <Pidgeot18@verizon.invalid> - 2011-05-15 22:38 -0400
                Re: Did the sort do anything? Lawrence D'Oliveiro <ldo@geek-central.gen.new_zealand> - 2011-05-16 19:11 +1200
                Re: Did the sort do anything? Lew <noone@lewscanon.com> - 2011-05-16 03:47 -0400
                Re: Did the sort do anything? markspace <-@.> - 2011-05-16 14:14 -0700
                Re: Did the sort do anything? Lew <noone@lewscanon.com> - 2011-05-15 22:40 -0400
                Re: Did the sort do anything? Tom Anderson <twic@urchin.earth.li> - 2011-05-16 21:31 +0100
                Re: Did the sort do anything? Lawrence D'Oliveiro <ldo@geek-central.gen.new_zealand> - 2011-05-17 09:12 +1200
                Re: Did the sort do anything? Lew <noone@lewscanon.com> - 2011-05-16 17:24 -0400
                Re: Did the sort do anything? Tom Anderson <twic@urchin.earth.li> - 2011-05-17 13:26 +0100
          Re: Did the sort do anything? markspace <-@.> - 2011-05-15 04:56 -0700
            Re: Did the sort do anything? Tom Anderson <twic@urchin.earth.li> - 2011-05-15 15:12 +0100
              Re: Did the sort do anything? markspace <-@.> - 2011-05-15 07:52 -0700
          Re: Did the sort do anything? Michael Wojcik <mwojcik@newsguy.com> - 2011-05-18 11:14 -0400
            Re: Did the sort do anything? Lew <noone@lewscanon.com> - 2011-05-18 13:02 -0400
            Re: Did the sort do anything? Lawrence D'Oliveiro <ldo@geek-central.gen.new_zealand> - 2011-05-20 18:49 +1200
              Re: Did the sort do anything? Robert Klemme <shortcutter@googlemail.com> - 2011-05-20 00:06 -0700
                Re: Did the sort do anything? Lawrence D'Oliveiro <ldo@geek-central.gen.new_zealand> - 2011-05-20 22:37 +1200
                Re: Did the sort do anything? Lew <noone@lewscanon.com> - 2011-05-20 07:09 -0400
  Re: Did the sort do anything? Andreas Leitgeb <avl@gamma.logic.tuwien.ac.at> - 2011-05-10 16:11 +0000
  Re: Did the sort do anything? Daniele Futtorovic <da.futt.news@laposte-dot-net.invalid> - 2011-05-10 21:26 +0200
    Re: Did the sort do anything? Tom Anderson <twic@urchin.earth.li> - 2011-05-11 21:38 +0100
      Re: Did the sort do anything? Daniele Futtorovic <da.futt.news@laposte-dot-net.invalid> - 2011-05-11 23:27 +0200
      Re: Did the sort do anything? Roedy Green <see_website@mindprod.com.invalid> - 2011-05-13 07:40 -0700
        Re: Did the sort do anything? Spock <spock@starfleet.ufp> - 2011-05-13 16:56 -0400
        Re: Did the sort do anything? Lawrence D'Oliveiro <ldo@geek-central.gen.new_zealand> - 2011-05-15 13:58 +1200
          Re: Did the sort do anything? Lew <noone@lewscanon.com> - 2011-05-14 23:27 -0400
  Re: Did the sort do anything? Robert Klemme <shortcutter@googlemail.com> - 2011-05-11 20:40 +0200
    Re: Did the sort do anything? Joshua Cranmer <Pidgeot18@verizon.invalid> - 2011-05-12 10:40 -0400
      Re: Did the sort do anything? Robert Klemme <shortcutter@googlemail.com> - 2011-05-13 03:50 -0700
      Re: Did the sort do anything? Roedy Green <see_website@mindprod.com.invalid> - 2011-05-13 07:46 -0700
        Re: Did the sort do anything? Lawrence D'Oliveiro <ldo@geek-central.gen.new_zealand> - 2011-05-16 14:32 +1200
          Re: Did the sort do anything? Patricia Shanahan <pats@acm.org> - 2011-05-15 19:50 -0700
            Re: Did the sort do anything? Lawrence D'Oliveiro <ldo@geek-central.gen.new_zealand> - 2011-05-16 17:57 +1200
              Re: Did the sort do anything? "javax.swing.JSnarker" <gharriman@boojum.mit.edu> - 2011-05-16 03:35 -0400
              Re: Did the sort do anything? Lew <noone@lewscanon.com> - 2011-05-16 03:44 -0400
              Re: Did the sort do anything? Patricia Shanahan <pats@acm.org> - 2011-05-16 03:53 -0700
                Re: Did the sort do anything? Lawrence D'Oliveiro <ldo@geek-central.gen.new_zealand> - 2011-05-17 00:02 +1200
                Re: Did the sort do anything? "javax.swing.JSnarker" <gharriman@boojum.mit.edu> - 2011-05-16 08:05 -0400
                Re: Did the sort do anything? Lawrence D'Oliveiro <ldo@geek-central.gen.new_zealand> - 2011-05-17 09:12 +1200
                Re: Did the sort do anything? Lew <noone@lewscanon.com> - 2011-05-16 17:32 -0400
                Re: Did the sort do anything? thoolen <thoolen@tholenbot.thorium> - 2011-05-16 18:09 -0400
                Re: Did the sort do anything? Lew <noone@lewscanon.com> - 2011-05-16 10:02 -0400
                Re: Did the sort do anything? Patricia Shanahan <pats@acm.org> - 2011-05-16 07:16 -0700
                Re: Did the sort do anything? Lawrence D'Oliveiro <ldo@geek-central.gen.new_zealand> - 2011-05-17 09:11 +1200
                Re: Did the sort do anything? Patricia Shanahan <pats@acm.org> - 2011-05-16 15:00 -0700
                Re: Did the sort do anything? Lew <noone@lewscanon.com> - 2011-05-16 21:08 -0400
                Re: Did the sort do anything? Lawrence D'Oliveiro <ldo@geek-central.gen.new_zealand> - 2011-05-17 19:11 +1200
                Re: Did the sort do anything? Patricia Shanahan <pats@acm.org> - 2011-05-17 02:34 -0700
                Re: Did the sort do anything? Lew <noone@lewscanon.com> - 2011-05-17 07:19 -0400
                [OT] Naming conventions. Was: Re: Did the sort do anything? Patricia Shanahan <pats@acm.org> - 2011-05-17 06:52 -0700
                Re: Naming conventions. Was: Re: Did the sort do anything? Robert Klemme <shortcutter@googlemail.com> - 2011-05-18 01:22 -0700
                Re: Naming conventions. Was: Re: Did the sort do anything? Patricia Shanahan <pats@acm.org> - 2011-05-18 03:42 -0700
                Re: Naming conventions. Was: Re: Did the sort do anything? RedGrittyBrick <RedGrittyBrick@spamweary.invalid> - 2011-05-18 11:53 +0100
                Re: Naming conventions. Was: Re: Did the sort do anything? Lew <noone@lewscanon.com> - 2011-05-18 13:07 -0400
                Re: Naming conventions. Was: Re: Did the sort do anything? Patricia Shanahan <pats@acm.org> - 2011-05-18 10:37 -0700
                Re: Naming conventions. Was: Re: Did the sort do anything? Heike Svensson <hsvensson.1093x1_q@hotmail.nospam.com.please> - 2011-05-19 01:29 -0400
                Re: Naming conventions. Was: Re: Did the sort do anything? Robert Klemme <shortcutter@googlemail.com> - 2011-05-19 08:28 +0200
                Re: Naming conventions. Was: Re: Did the sort do anything? Lew <noone@lewscanon.com> - 2011-05-19 08:50 -0400
                OT: National stereotypes. Was Re: Naming conventions. Was: Re: Did the sort do anything? RedGrittyBrick <RedGrittyBrick@spamweary.invalid> - 2011-05-23 10:25 +0100
                Re: OT: National stereotypes. Was Re: Naming conventions. Was: Re: Did the sort do anything? Lew <noone@lewscanon.com> - 2011-05-23 09:05 -0400
                Re: OT: National stereotypes. Was Re: Naming conventions. Was: Re: Did the sort do anything? RedGrittyBrick <RedGrittyBrick@spamweary.invalid> - 2011-05-23 17:17 +0100
                Re: OT: National stereotypes. Was Re: Naming conventions. Was: Re: Did the sort do anything? Lew <noone@lewscanon.com> - 2011-05-23 14:43 -0400
                Re: OT: National stereotypes. Was Re: Naming conventions. Was: Re: Did the sort do anything? Steve Sobol <sjsobol@JustThe.net> - 2011-05-23 08:27 -0700
                Re: OT: National stereotypes. Was Re: Naming conventions. Was: Re: Did the sort do anything? RedGrittyBrick <RedGrittyBrick@spamweary.invalid> - 2011-05-23 17:39 +0100
                Re: OT: National stereotypes. Was Re: Naming conventions. Was: Re:   Did the sort do anything? Robert Klemme <shortcutter@googlemail.com> - 2011-05-23 19:16 +0200
                Re: OT: National stereotypes. Was Re: Naming conventions. Was: Re: Did the sort do anything? Lew <noone@lewscanon.com> - 2011-05-23 14:47 -0400
                Re: Did the sort do anything? Boojum <boojum42@gmai1.c0m> - 2011-05-18 07:19 -0400
                Re: Did the sort do anything? Lawrence D'Oliveiro <ldo@geek-central.gen.new_zealand> - 2011-05-20 18:46 +1200
                Re: Did the sort do anything? Lew <noone@lewscanon.com> - 2011-05-20 07:10 -0400
                Re: Did the sort do anything? Lew <noone@lewscanon.com> - 2011-05-17 07:16 -0400
                Re: Did the sort do anything? Patricia Shanahan <pats@acm.org> - 2011-05-17 06:56 -0700
                Re: Did the sort do anything? Lawrence D'Oliveiro <ldo@geek-central.gen.new_zealand> - 2011-05-20 18:46 +1200
                Re: Did the sort do anything? Lew <noone@lewscanon.com> - 2011-05-20 07:11 -0400
                Re: Did the sort do anything? Patricia Shanahan <pats@acm.org> - 2011-05-20 05:00 -0700
                Re: Did the sort do anything? Patricia Shanahan <pats@acm.org> - 2011-05-20 05:20 -0700
                Re: Did the sort do anything? Lawrence D'Oliveiro <ldo@geek-central.gen.new_zealand> - 2011-05-21 09:56 +1200
                Re: Did the sort do anything? Lew <noone@lewscanon.com> - 2011-05-20 18:12 -0400
                Re: Did the sort do anything? Patricia Shanahan <pats@acm.org> - 2011-05-20 21:26 -0700
                Re: Did the sort do anything? Gheerax IV <gheerax.4@gmail.invalid> - 2011-05-17 06:58 +0000
                Re: Did the sort do anything? Unitary Matrix <umatrix668@gmail.com> - 2011-05-17 00:13 -0700
                Re: Did the sort do anything? markspace <-@.> - 2011-05-17 07:41 -0700
    Re: Did the sort do anything? Roedy Green <see_website@mindprod.com.invalid> - 2011-05-13 07:42 -0700
      Re: Did the sort do anything? Robert Klemme <shortcutter@googlemail.com> - 2011-05-13 21:28 +0200
  Re: Did the sort do anything? Tom Anderson <twic@urchin.earth.li> - 2011-05-11 21:32 +0100

csiph-web