quick sort

qs.rkt

#lang racket/base
(require racket/match
         racket/list
         racket/sequence
         racket/random)

(define (is l)
  (define (insert x ys)
    (match ys
      [(list) (list x)]
      [(cons y rst) (cond [(< x y) (cons x ys)]
                          [else (cons y (insert x rst))])]))
  (foldl insert '() l))
(define/match (qs l)
  [('()) '()]
  [(l) #:when (<= (length l) 6) (is l)]
  [(_) (define p (random-ref l))
       (append (qs (filter (λ (e) (< e p)) l))
               (list p)
               (qs (filter (λ (e) (> e p)) l)))])

(define l (sequence->list (in-range 1000000)))
(define tl (shuffle l))

(time
 (for ([i (in-range 1)])
   (equal? (qs tl) l)))

(define/match (q3 l)
  [('()) '()]
  [(l) #:when (<= (length l) 6) (is l)]
  [(lst)
   (define index (+ (random (add1 (quotient (length lst) 2)))
                    (random (add1 (quotient (length lst) 2)))))
   (define pivot (list-ref lst (max 0 (sub1 index))))
   (append (q3 (filter (λ (x) (< x pivot)) lst))
           (list pivot)
           (q3 (filter (λ (x) (> x pivot)) lst)))])

(time
 (for ([i (in-range 1)])
   (equal? (q3 tl) l)))

list length	qs	q3
10000	9.16ms	4.6ms
100000	116.4ms	60.3ms
1000000	1653.7ms	945.6ms