#| Template
1. Trivial case(s):
The problem is solved if the input list is empty.
2. Divide:
Create a list of items smaller than the pivot (first item) and another
list of items larger than the pivot.  Then sort each of these lists.
3. Conquer:
Append the sorted list of smaller items, the pivot, and the sorted list
of larger items.
|#

;; kwik-sort : (listof Number) -> (listof Number)
;; sort a list of distinct numbers
;; uses the quicksort strategy
(define (kwik-sort alon)
  (cond
    [(empty? alon) alon]
    [else {local [(define pivot (first alon))]
            (append
             (kwik-sort (smaller-items (rest alon) pivot))
             (list pivot)
             (kwik-sort (larger-items (rest alon) pivot)))}]))

;; smaller-items : (listof Number) Number -> (listof Number)
;; produce a list containing all numbers in alon less than pivot
(define (smaller-items alon pivot)
  (filter (lambda (x) (< x pivot)) alon))

;; larger-items : (listof Number) Number -> (listof Number)
;; produce a list containing all numbers in alon greater than pivot
(define (larger-items alon pivot)
  (filter (lambda (x) (> x pivot)) alon))

;; examples/tests of helpers
(equal?
 (smaller-items (list 5 1 4 2 3) 2)
 (list 1))
(equal?
 (larger-items (list 5 1 4 2 3) 2)
 (list 5 4 3))

;; example/test of kwik-sort
(equal?
 (kwik-sort (list 4 6 3 10 2 7 8 1))
 (list 1 2 3 4 6 7 8 10))