Re: Simple Sort - the smallest sorting routine?

From	Bernd Paysan <bernd.paysan@gmx.de>
Newsgroups	comp.lang.forth
Subject	Re: Simple Sort - the smallest sorting routine?
Date	2013-07-09 23:39 +0200
Organization	1&1 Internet AG
Message-ID	<krhvve$mpr$1@online.de> (permalink)
References	(7 earlier) <2013Jul7.115901@mips.complang.tuwien.ac.at> <vOWdnbVSbJX7y0TMnZ2dnUVZ_uWdnZ2d@supernews.com> <2013Jul7.141859@mips.complang.tuwien.ac.at> <wKKdnVVMtarQT0fMnZ2dnUVZ_vednZ2d@supernews.com> <2013Jul9.162517@mips.complang.tuwien.ac.at>

Show all headers | View raw

Anton Ertl wrote:
> Thanks.  I added a middle-pivot variant, and middle pivot with special
> treatment of 2 elements as suggested by Bernd Paysan

The insert sort (an O(n²) algorithm) used by this code is sufficiently 
faster than quicksort, that for somewhere between 16 and 64 items, it is 
better to switch to insert sort.  The difference is still small (~20%).

The reason why insert sort is sufficiently better is predictability: insert 
sort(a,n) has just n+1 branch misses, while quicksort(a,n) has a pretty bad 
prediction rate (n/2 log n mispredictions).

And remember: O(n²) is really n*n/2, so n*log n for n=16 is 16*4 operations, 
while O(n²) for n=16 is just 16*8 operations.  Not too many more, and since 
the prediction is better, it's faster.  The difference however is small, but 
it is stable for more complex compares (strings), because insert sort also 
needs fewer compares for smaller sizes.

-- 
Bernd Paysan
"If you want it done right, you have to do it yourself"
http://bernd-paysan.de/

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

Thread

Simple Sort - the smallest sorting routine? The Beez <the.beez.speaks@gmail.com> - 2013-06-25 13:12 -0700
  Re: Simple Sort - the smallest sorting routine? Mark Wills <markrobertwills@yahoo.co.uk> - 2013-06-25 23:48 -0700
    Re: Simple Sort - the smallest sorting routine? The Beez <the.beez.speaks@gmail.com> - 2013-06-26 09:11 -0700
  Re: Simple Sort - the smallest sorting routine? m.a.m.hendrix@tue.nl - 2013-06-26 02:03 -0700
  Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-06-26 11:25 -0500
    Re: Simple Sort - the smallest sorting routine? the_gavino_himself <visphatesjava@gmail.com> - 2013-06-26 12:36 -0700
      Re: Simple Sort - the smallest sorting routine? "Elizabeth D. Rather" <erather@forth.com> - 2013-06-26 09:49 -1000
    Re: Simple Sort - the smallest sorting routine? "WJ" <w_a_x_man@yahoo.com> - 2013-06-26 20:24 +0000
  Re: Simple Sort - the smallest sorting routine? "WJ" <w_a_x_man@yahoo.com> - 2013-06-26 20:23 +0000
    Re: Simple Sort - the smallest sorting routine? Alex McDonald <blog@rivadpm.com> - 2013-06-26 13:35 -0700
      Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-06-26 16:37 -0700
        Re: Simple Sort - the smallest sorting routine? The Beez <the.beez.speaks@gmail.com> - 2013-06-27 01:31 -0700
          Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-06-27 04:04 -0500
          Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-06-30 09:27 -0700
            Re: Simple Sort - the smallest sorting routine? Alex McDonald <blog@rivadpm.com> - 2013-06-30 13:23 -0700
            Re: Simple Sort - the smallest sorting routine? "Alex McDonald" <blog@rivadpm.com> - 2013-06-30 21:48 +0100
              Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-06-30 16:53 -0700
                Re: Simple Sort - the smallest sorting routine? Alex McDonald <blog@rivadpm.com> - 2013-07-01 04:34 -0700
                Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-03 18:41 -0700
                Re: Simple Sort - the smallest sorting routine? Alex McDonald <blog@rivadpm.com> - 2013-07-04 02:58 -0700
                Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-04 21:30 -0700
                Re: Simple Sort - the smallest sorting routine? "Alex McDonald" <blog@rivadpm.com> - 2013-07-06 00:18 +0100
                Re: Simple Sort - the smallest sorting routine? Bernd Paysan <bernd.paysan@gmx.de> - 2013-07-06 13:45 +0200
                Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-06 07:49 -0500
                Re: Simple Sort - the smallest sorting routine? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-07-06 13:38 +0000
                Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-06 10:06 -0500
                Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-06 23:08 -0700
                Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-07 06:24 -0500
                Re: Simple Sort - the smallest sorting routine? Bernd Paysan <bernd.paysan@gmx.de> - 2013-07-07 23:47 +0200
                Re: Simple Sort - the smallest sorting routine? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-07-07 09:59 +0000
                Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-07 06:52 -0500
                Re: Simple Sort - the smallest sorting routine? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-07-07 12:18 +0000
                Re: Simple Sort - the smallest sorting routine? m.a.m.hendrix@tue.nl - 2013-07-08 00:06 -0700
                Re: Simple Sort - the smallest sorting routine? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-07-08 09:50 +0000
                Re: Simple Sort - the smallest sorting routine? m.a.m.hendrix@tue.nl - 2013-07-08 03:14 -0700
                Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-08 09:53 -0500
                Re: Simple Sort - the smallest sorting routine? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-07-09 14:25 +0000
                Re: Simple Sort - the smallest sorting routine? Bernd Paysan <bernd.paysan@gmx.de> - 2013-07-09 23:39 +0200
                Re: Simple Sort - the smallest sorting routine? Paul Rubin <no.email@nospam.invalid> - 2013-07-09 18:03 -0700
                Re: Simple Sort - the smallest sorting routine? Bernd Paysan <bernd.paysan@gmx.de> - 2013-07-10 23:05 +0200
                Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-10 03:21 -0500
                Re: Simple Sort - the smallest sorting routine? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-07-10 10:29 +0000
                Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-10 05:44 -0500
                Re: Simple Sort - the smallest sorting routine? Paul Rubin <no.email@nospam.invalid> - 2013-07-10 04:07 -0700
                Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-10 06:06 -0500
                Re: Simple Sort - the smallest sorting routine? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-07-10 14:21 +0000
                Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-10 04:45 -0500
                Re: Simple Sort - the smallest sorting routine? Paul Rubin <no.email@nospam.invalid> - 2013-07-10 03:13 -0700
                Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-10 05:09 -0500
                Re: Simple Sort - the smallest sorting routine? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-07-10 12:16 +0000
                Re: Simple Sort - the smallest sorting routine? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-07-10 10:38 +0000
                Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-10 06:45 -0500
                Re: Simple Sort - the smallest sorting routine? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-07-10 13:56 +0000
                Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-10 10:54 -0700
                Re: Simple Sort - the smallest sorting routine? Alex McDonald <blog@rivadpm.com> - 2013-07-10 13:57 -0700
                Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-10 07:15 -0500
                Re: Simple Sort - the smallest sorting routine? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-07-10 13:52 +0000
                Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-10 15:00 -0500
                Re: Simple Sort - the smallest sorting routine? Coos Haak <chforth@hccnet.nl> - 2013-07-10 16:13 +0200
                Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-10 17:07 -0500
                Re: Simple Sort - the smallest sorting routine? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-07-11 10:53 +0000
                Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-11 10:40 -0700
                Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-11 15:17 -0500
                Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-11 16:54 -0700
                Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-12 03:07 -0500
                Re: Simple Sort - the smallest sorting routine? Bernd Paysan <bernd.paysan@gmx.de> - 2013-07-07 00:43 +0200
                Re: Simple Sort - the smallest sorting routine? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-07-07 00:21 +0000
                Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-06 20:32 -0700
                Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-07 06:38 -0500
                Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-07 07:05 -0500
                Re: Simple Sort - the smallest sorting routine? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-07-07 13:00 +0000
                Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-07 09:47 -0700
                Re: Simple Sort - the smallest sorting routine? "Alex McDonald" <blog@rivadpm.com> - 2013-07-07 21:22 +0100
                Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-07 19:25 -0500
                Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-07 21:58 -0700
                Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-08 02:27 -0500
                Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-08 21:18 -0700
                Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-09 04:20 -0500
                Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-10 10:30 -0700
                Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-10 15:13 -0500
                Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-10 13:57 -0700
                Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-10 16:57 -0500
                Re: Simple Sort - the smallest sorting routine? Elizabeth D Rather <erather@forth.com> - 2013-07-10 13:00 -1000
                Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-10 22:19 -0700
                Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-11 10:23 -0700
                Re: Simple Sort - the smallest sorting routine? Bernd Paysan <bernd.paysan@gmx.de> - 2013-07-11 01:12 +0200
                Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-11 00:33 -0500
                Re: Simple Sort - the smallest sorting routine? Bernd Paysan <bernd.paysan@gmx.de> - 2013-07-11 11:48 +0200
                Re: Simple Sort - the smallest sorting routine? Paul Rubin <no.email@nospam.invalid> - 2013-07-11 03:08 -0700
                Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-11 05:00 -0500
                Re: Simple Sort - the smallest sorting routine? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-07-11 10:17 +0000
                Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-11 06:53 -0500
                Re: Simple Sort - the smallest sorting routine? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-07-11 15:21 +0000
                Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-11 10:37 -0500
                Re: Simple Sort - the smallest sorting routine? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-07-11 17:07 +0000
                Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-11 15:19 -0500
                Re: Simple Sort - the smallest sorting routine? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-07-11 17:33 +0000
                Re: Simple Sort - the smallest sorting routine? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-07-11 18:18 +0000
                Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-11 16:46 -0700
                Re: Simple Sort - the smallest sorting routine? Alex McDonald <blog@rivadpm.com> - 2013-07-12 03:48 -0700
                Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-12 10:55 -0700
                Re: Simple Sort - the smallest sorting routine? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-07-12 19:29 +0000
                Re: Simple Sort - the smallest sorting routine? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-07-15 09:50 +0000
                Re: Simple Sort - the smallest sorting routine? Alex McDonald <blog@rivadpm.com> - 2013-07-12 13:22 -0700
                Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-13 20:05 -0700
                Re: Simple Sort - the smallest sorting routine? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-07-14 11:34 +0000
                Re: Simple Sort - the smallest sorting routine? Alex McDonald <blog@rivadpm.com> - 2013-07-14 09:18 -0700
                Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-14 16:05 -0700
                Re: Simple Sort - the smallest sorting routine? Ron Aaron <rambamist@gmail.com> - 2013-07-15 06:12 +0300
                Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-14 22:17 -0700
                Re: Simple Sort - the smallest sorting routine? Ron Aaron <rambamist@gmail.com> - 2013-07-15 11:44 +0300
                Re: Simple Sort - the smallest sorting routine? Alex McDonald <blog@rivadpm.com> - 2013-07-15 09:42 -0700
                Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-16 18:03 -0700
                Re: Simple Sort - the smallest sorting routine? Alex McDonald <blog@rivadpm.com> - 2013-07-17 00:54 -0700
                Re: Simple Sort - the smallest sorting routine? Howerd <howerdo@yahoo.co.uk> - 2013-07-14 10:09 -0700
                Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-14 15:35 -0700
                Re: Simple Sort - the smallest sorting routine? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-07-11 17:08 +0000
                Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-11 15:30 -0500
                Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-11 09:34 -0700
                Re: Simple Sort - the smallest sorting routine? Michael Morris <morrimichael@gmail.com> - 2013-07-15 23:09 -0500
                Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-16 17:46 -0700
                Re: Simple Sort - the smallest sorting routine? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-07-17 03:14 -0500
                Re: Simple Sort - the smallest sorting routine? "Rod Pemberton" <do_not_have@notemailnotq.cpm> - 2013-07-17 21:47 -0400
                Re: Simple Sort - the smallest sorting routine? "Alex McDonald" <blog@rivadpm.com> - 2013-07-11 04:06 +0100
                Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-06 20:18 -0700
                Re: Simple Sort - the smallest sorting routine? "Alex McDonald" <blog@rivadpm.com> - 2013-07-07 16:48 +0100
                Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-07 09:13 -0700
                Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-07-07 09:13 -0700
                Re: Simple Sort - the smallest sorting routine? "Alex McDonald" <blog@rivadpm.com> - 2013-07-07 21:24 +0100
                Re: Simple Sort - the smallest sorting routine? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-07-04 14:41 +0000
        Re: Simple Sort - the smallest sorting routine? Alex McDonald <blog@rivadpm.com> - 2013-06-27 01:59 -0700
          Re: Simple Sort - the smallest sorting routine? hughaguilar96@yahoo.com - 2013-06-30 09:30 -0700
            Re: Simple Sort - the smallest sorting routine? Alex McDonald <blog@rivadpm.com> - 2013-06-30 12:59 -0700
    Re: Simple Sort - the smallest sorting routine? awegel@arcor.de (Alex Wegel) - 2013-06-27 00:08 +0200
    Re: Simple Sort - the smallest sorting routine? Doug Hoffman <glidedog@gmail.com> - 2013-06-26 19:31 -0400
      Re: Simple Sort - the smallest sorting routine? Doug Hoffman <glidedog@gmail.com> - 2013-06-27 06:26 -0400
  Re: Simple Sort - the smallest sorting routine? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-06-28 02:05 +0000
    Re: Simple Sort - the smallest sorting routine? Alex McDonald <blog@rivadpm.com> - 2013-07-04 07:33 -0700
      Re: Simple Sort - the smallest sorting routine? Coos Haak <chforth@hccnet.nl> - 2013-07-05 00:47 +0200
        Re: Simple Sort - the smallest sorting routine? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-07-14 19:01 +0000
          Re: Simple Sort - the smallest sorting routine? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-07-15 01:28 +0000
        Re: Simple Sort - the smallest sorting routine? Ian Osgood <iano@quirkster.com> - 2013-07-19 11:29 -0700
  Re: Simple Sort - the smallest sorting routine? Brad Eckert <hwfwguy@gmail.com> - 2013-07-19 09:09 -0700

csiph-web