Path: csiph.com!usenet.pasdenom.info!aioe.org!news.mb-net.net!news.babsi.de!open-news-network.org!news2.open-news-network.org!.POSTED!not-for-mail
From: Mark Carroll <mtbc@bcs.org>
Newsgroups: comp.lang.postscript
Subject: Re: YA quicksort function
Date: Sun, 25 Aug 2013 09:50:28 +0100
Organization: none
Lines: 111
Message-ID: <87li3qf92j.fsf@ixod.org>
References: <a0e13204-b665-45bb-92c8-724d97d82482@googlegroups.com>
NNTP-Posting-Host: 82-71-47-217.dsl.in-addr.zen.co.uk
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
X-Trace: news2.open-news-network.org 1377420628 23019 82.71.47.217 (25 Aug 2013 08:50:28 GMT)
X-Complaints-To: abuse@open-news-network.org
NNTP-Posting-Date: Sun, 25 Aug 2013 08:50:28 +0000 (UTC)
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/23.4 (gnu/linux)
Cancel-Lock: sha1:TgA7S1q/bLhlk9wcBQrvQzdx6dA=
Xref: csiph.com comp.lang.postscript:1595

For what it's worth, years ago I wrote a mergesort,

/sortarray
{
  8 dict begin
  
  /lessthan exch def

  dup length 0 gt
  {
    /mergetwo
    {
      /first exch def
      /second exch def
      /result first length second length add array def
      
      /firstat 0 def
      /secondat 0 def     

      0 1 result length 1 sub
      {
        /resultat exch def

        firstat first length eq
        {
          result resultat second secondat second length secondat sub getinterval putinterval
          exit
        }
        if

        secondat second length eq
        {
          result resultat first firstat first length firstat sub getinterval putinterval
          exit
        }
        if

        /firstelement first firstat get def
        /secondelement second secondat get def
        
        firstelement secondelement lessthan
        {
          result resultat firstelement put
          /firstat firstat 1 add def
        }
        {
          result resultat secondelement put
          /secondat secondat 1 add def
        }
        ifelse
      }
      for

      result
    } def
    
    /mergeall
    {
      dup length 1 eq
      {
        0 get
      }
      {
        /previous exch def
        
        previous length 2 mod 0 eq
        {
          /next previous length 2 idiv array def
          /nextat 0 def

          0
        }
        {
          /next previous length 2 idiv 1 add array def
          /nextat 1 def

          next 0 previous 0 get put

          1
        }
        ifelse

        2 previous length 2 sub
        {
          dup 1 add previous exch get exch previous exch get mergetwo
          next nextat 3 -1 roll put
          /nextat nextat 1 add def
        }
        for

        next mergeall
      }
      ifelse
    } def
    
    [ exch { 1 array dup 3 1 roll 0 3 -1 roll put } forall ] mergeall
  }
  if

  end
} bind def

I'm not going to claim that it is all that great, and it badly needs
comments, but it works.

GS>[ (one) (two) (three) (four) (five) (six) ] { lt } sortarray ==
[(five) (four) (one) (six) (three) (two)]
GS>[ 1 2 9 8 7 4 5 6 3 ] { gt } sortarray ==     
[9 8 7 6 5 4 3 2 1]

-- Mark