;; [List-of Number] -> [List-of Number]

;; WHAT: sort the given list of numbers in ascending order 

;; HOW : determine pivot, sort those numbers smaller and larger 
;;       than pivot separately, append results with pivot in middle 

;; TERMINATES for all possible input lists because 
;; the recursive calls are guaranteed to receive smaller lists
;; than the given l

(check-expect (quick-sort '(3 1 2 4 0)) '(0 1 2 3 4))
(check-expect (quick-sort '(2 1 3 4 0)) '(0 1 2 3 4))

(define (quick-sort l)
  (cond
    ;; -------------------------------------------------------
    ;; trivial problems: 
    [(empty? l) l]
    [(one? l) l]
    [(two? l) (list (apply min l) (apply max l))]
    ;; -------------------------------------------------------
    [(cons? l)
     (local (;; ----------------------------------------------
             ;; splitting the problem 
             (define pivot   (first l))
             (define equals* (filter (lambda (n) (= n pivot)) l))
             (define smalls* (filter (lambda (n) (< n pivot)) l))
             (define large*  (filter (lambda (n) (> n pivot)) l))
             ;; ----------------------------------------------
             ;; recursively solve 
             (define small-sorted (quick-sort smalls*))
             (define large-sorted (quick-sort large*)))
       ;; ----------------------------------------------------
       ;; combine solutions: 
       (append small-sorted equals* large-sorted))]))



;; wish list:
;; ---------------------------------

;; [List-of X] -> Boolean
;; does this list contain two items? 

(define (two? l)
  false)

;; [List-of X] -> Boolean
;; does this list contain exactly one item? 

(define (one? l)
  false)