;;
;; *************************************************
;;
;; CS 135 Assignment 9, Question 6
;; 
;;
;; *************************************************
;;

;; Contract: insertion-sort: (List of X) (X -> boolean) -> (List of X)
;; Purpose: Sorts a list of X by comparing with supplied function
;; Examples:
;; (insertion-sort '(1 2 3 4 5) >) => '(5 4 3 2 1)
;; (insertion-sort '(5 2 3 4 1) <) => '(1 2 3 4 5)

(define (insertion-sort alox cmp)
  (local ((define (insert x alox cmp)
            (cond
              [(empty? alox) (cons x empty)]
              [else
               (cond
                 [(cmp x (first alox))(cons x alox)]
                 [else (cons (first alox)(insert x (rest alox) cmp))])]))
          (define (ins-sort-acc sorted unsorted cmp)
            (cond
              [(empty? unsorted) sorted]
              [else (ins-sort-acc (insert (first unsorted) sorted cmp) (rest unsorted) cmp)])))
  (ins-sort-acc empty alox cmp)))

(equal? (insertion-sort '(1 6 2 3 4 6) <) '(1 2 3 4 6 6))
(equal? (insertion-sort '(1 4 3 2 1) >) '(4 3 2 1 1))
(equal? (insertion-sort '(2) <) '(2))