;;; sorts.ss
;;;   A set of sorting routines.
;;; Author
;;;   Samuel A. Rebelsky
;;; Version
;;;   1.0 of April 1998
;;; Requires
;;;   utils.ss
;;; Copyright (c) Samuel A. Rebelsky.  All rights reserved.

;;; Sort a list of numbers using the legendary quick sort procedure.
;;; We pick a pivot, split the list into three parts: smaller than the
;;; pivot, equal to the pivot, and greater than the pivot.  We then
;;; recursively sort the smaller and lesser sublists and join the results
;;; together.
(define (quicksort lst)
  (if (null? lst) nil
      (let ((pivot (car lst)))
         (append 
            (quicksort (select (lambda (x) (< x pivot)) lst))
            (select (lambda (x) (= x pivot)) lst)
            (quicksort (select (lambda (x) (> x pivot)) lst))))))

;;; Sort a list of numbers using the legendary merge sort procedure.
;;; In the recursive version of this procedure, we split the list in
;;; half, sort the two halves, and then merge the results.  I've
;;; decided that it's okay to rearrange the list when splitting.
(define (mergesort lst)
  ; First base case: empty list
  (if (null? lst) nil
  ; Second base case: single element list
  (if (null? (cdr lst)) lst
  ; Recursive case: split, sort the two halves, then merge
      (let ((halves (split lst)))
         (merge (mergesort (car halves))
                (mergesort (cdr halves)))))))

;;; Split a list into two lists of approximately the same size.
;;; Postcondition: each element in the original list appears exactly
;;;   once in one of the two lists
;;; Postcondition: the two lists differ in length by at most 1.
;;; Returns: a list whose car is the first list and
;;;   whose cdr is the second list.
;;; Note: May rearrange the elements.
(define (split lst)
  (letrec ((splithelper (lambda (lst first second add-to-first)
             (if (null? lst)
                 (cons first second)
                 (if add-to-first
                     (splithelper (cdr lst) 
                                  (cons (car lst) first) 
                                  second
                                  #f)
                     (splithelper (cdr lst) 
                                  first
                                  (cons (car lst) second) 
                                  #t)
                 ) ; if add-to-first
             ) ; if the lst is null
           ))) ;;; variables in the letrec
     (splithelper lst nil nil #t)
  ) ; letrec
) ; define split

;;; Merge two sorted lists into a sorted list
(define (merge first second)
  (if (null? first) second
  (if (null? second) first
  (if (< (car first) (car second))
      (cons (car first) (merge (cdr first) second))
      (cons (car second) (merge first (cdr second)))))))

;;; Sort a list by using the insertion sort procedure.  We sort the
;;; cdr of the list and then insert the element in the appropriate
;;; place in that list.
(define (insertion-sort lst)
  ; Base case: empty list
  (if (null? lst) lst
  ; Recursive case: sort the cdr and insert
      (insert (car lst) (insertion-sort (cdr lst)))))

;;; Insert an element into the appropriate place in a sorted list.
(define (insert elt lst)
  ; Base case one, empty list: create a new list containing the element
  (if (null? lst) (list elt)
  ; Base case two, element falls before the first element in the list:
  ;   cons 'em together
  (if (< elt (car lst)) (cons elt lst)
  ; Recursive case: insert into remainder of list
      (cons (car lst) (insert elt (cdr lst))))))

;;; Sort a list using a variant of the quicksort procedure.
;;; ** This is an incorrect sorting procedure, but it seems to
;;;    correctly sort many "randomly generated" lists. **
(define (qsort lst)
  (if (null? lst) nil
      (let ((pivot (car lst)))
         (append
            (quicksort (select (lambda (x) (< x pivot)) lst))
            (list pivot)
            (quicksort (select (lambda (x) (> x pivot)) lst))))))

;;; Sort a list using the legendary mrgsort procedure that splits
;;; the list in two, sorts the first half, and merges them togeter.
;;; ** This is an incorrect sorting procedure. **
(define (mrgsort lst)
  (if (null? lst) nil
  (if (null? (cdr lst)) lst
      (let ((halves (split lst)))
         (merge (mrgsort (car halves))
                (cdr halves))))))

;;; Sort a list, or at least pretend to sort the list.
(define (foosort lst)
  '(1 2 3))