a bit edited version of http://stackoverflow.com/questions/20688957/can-i-implement-quicksort-efficiently-with-scheme/20691734#20691734

quicksort-sheep-trick.scm

;; http://stackoverflow.com/a/20691734/849891  answered Dec 19 '13 at 21:10 
;; by Joshua Taylor

Although there's already an accepted answer, I thought you might appreciate a Scheme 
translation of the [Sheep Trick from _The Pitmanual_][1].  Your code is actually 
quite similar to it already.  Scheme does support `do` loops, but they're not 
particularly idiomatic, whereas named `let`s are much more common, so I've used the 
latter in this code.  As you've noted, choosing the first element as the pivot cause 
perfomance problems if the list is already sorted.  Since you have to traverse the 
list on each iteration, there might be some clever thing you could do to pick the 
pivots for the left and right sides  for the recursive calls in advance. 

<!-- language: scheme -->

    (define (nconc a b)                 ; Destructively concatenate a and b:
      (cond
        ((null? a) b)                   ; If a is empty, return b. 
        (else (let loop ((p a))         ; Otherwise,
                  (if (null? (cdr p))   ;   if it's the last pair of a,
                    (set-cdr! p b)      ;     set its cdr to b,
                    (loop (cdr p))))    ;     else continue
              a)))                      ;   and return a in the end
    
    (define (quicksort lst)
      (if (null? lst) lst
          (let ((pv  (car lst))         ; pivot
                (lt  '())               ; left
                (rt  '()))              ; right
            (let loop ((p (cdr lst)))   ; start with pointer at rest of lst, after pivot
              (if (null? p)
                  (nconc (quicksort lt)
                         (cons pv
                               (quicksort rt)))
                  (let ((t (cdr p)))          ; set aside for later
                    (cond
                        ((< (car p) pv) 
                             (set-cdr! p lt)  ; weave onto left
                             (set! lt  p))
                        (else
                             (set-cdr! p rt)  ; weave onto right
                             (set! rt  p)))
                    (loop t)))))))

<!-- -->
    
    (quicksort (list 9 1 8 2 7 3 6 4 5))
    ;=> (1 2 3 4 5 6 7 8 9)


Scheme does support `do`, so if you are interested in that (it does make 
the Common Lisp and Scheme version very similar), it looks like this 
(with three-way partitioning added - w.n.): 

<!-- language: scheme -->

    (define (quicksort ls)
      (if (null? ls) ls
        (let* ((p  (cdr ls))             ; a pointer along the rest of input list
               (pv (car ls))             ; pivot
               (t  (set-cdr! ls '())))   ; `ls` is used as middle section
          (do ((p   p   t)               ; `t` is a temp var
               (lt  '()) 
               (rt  '()))
              ((null? p) (nconc (quicksort lt)
                                (nconc ls (quicksort rt))))
            (set! t (cdr p))             ; set aside the rest
            (cond                        ; and weave the first into one of sections
              ((< (car p) pv) (begin (set-cdr! p lt) (set! lt p)))
              ((= (car p) pv) (begin (set-cdr! p ls) (set! ls p)))
              ((> (car p) pv) (begin (set-cdr! p rt) (set! rt p))))))))


<!-- -->
    
    (display (quicksort (list 9 1 8 2 7 3 6 4 5)))
    ;=> (1 2 3 4 5 6 7 8 9)


  [1]: http://www.maclisp.info/pitmanual/funnies.html#sheep_trick

____
The sheep trick code, slightly edited, is


     (defmacro weave-into (x y)
       `(setq ,y (rplacd (prog1 ,x 
                                (setq ,x (cdr ,x)))
                         ,y)))
    
     (defun quicksort (list judge)
       (if (null list)
           ()    
           (do ((proof (pop list))  
                (goats ())         
                (sheep ()))
               ((null list)
                (nconc (quicksort goats judge)
                       (cons proof                
                             (quicksort sheep judge))))
             (if (funcall judge (car  list) proof)   
                 (weave-into list goats)
                 (weave-into list sheep)))))

of course nconc will have to re-trace the first half; this is silly. must rearrange by adding one more argument for "do-next" ((( continuation, anyone? ))) a-la my quicksort3. will do some time later.