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-07 23:47 +0200
Organization	1&1 Internet AG
Message-ID	<krcnm4$r03$1@online.de> (permalink)
References	(9 earlier) <UI-dnWjgNLTHj0XMnZ2dnUVZ_oGdnZ2d@supernews.com> <2013Jul6.153838@mips.complang.tuwien.ac.at> <5PednZKx29YYr0XMnZ2dnUVZ_qudnZ2d@supernews.com> <5d589d1d-8962-468b-8508-f4fb15164c68@googlegroups.com> <XvqdnQs9191H0kTMnZ2dnUVZ_r6dnZ2d@supernews.com>

Show all headers | View raw

Andrew Haley wrote:

> For 1000 integer elements, Intel Core i5 M 480 @ 2.67GHz
> 
> median-of-3 quicksort:
> 
> quick_sort all data the same: 19us
> quick_sort already sorted: 11us
> quick_sort reversed: 11us
> quick_sort random data: 56us

Looks pretty fast.  bigForth's qsort (middle pivot) takes ~120µs for 1000 
random integers, and ~60µs for sorted, Core i7 @ 3GHz (in turbo mode).  I 
tried hand-optimizing the swap two elements section (no push/pop involved), 
but it didn't improve anything.

Given my measurements, I'm not convinced that quicksort is really so bad for 
small sizes.  I would probably use "swapsort" for arrays of size 2, but 
anything beyond that is not really worth investigating.

I do tail recursion for the larger array half, and real recursion for the 
smaller.

-- 
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