Cacher is the code snippet organizer for pro developers

;; scheme: chicken scheme
;; Author: Carlos Perilla <deepspawn AT valkertown.org>
;; Date: 25-10-2013

;; http://programmingpraxis.com/2013/10/25/pessimal-algorithms-and-simplexity-analysis/

;;     The slowsort algorithm is a perfect illustration of the multiply
;; and surrender paradigm, which is perhaps the single most important
;; paradigm in the development of reluctant algorithms. The basic
;; multiply and surrender strategy consists in replacing the problem at
;; hand by two or more subproblems, each slightly simpler than the
;; original, and continue multiplying subproblems and subsubproblems
;; recursively in this fashion as long as possible. At some point the
;; subproblems will all become so simple that their solution can no
;; longer be postponed, and we will have to surrender. Experience shows
;; that, in most cases, by the time this point is reached the total work
;; will be substantially higher than what could have been wasted by a
;; more direct approach.

;;     To get a firmer grasp of the multiply and surrender method, let us
;; follow the step-by-step development of the slowsort algorithm. We can
;; decompose the problem of sorting n numbers Al, A2, …, An in ascending
;; order into (1) finding the maximum of those numbers, and (2) sorting
;; the remaining ones. Subproblem (1) can be further decomposed
;; into (1.1) find the maximum of the first [n/2] elements, (1.2) find the
;; maximum of the remaining [n/2] elements, and (1.3) find the largest of
;; those two maxima. Finally, subproblems (1.1) and (1.2) can be solved
;; by sorting the specified elements and taking the last element in the
;; result. We have thus multiplied the original problem into three
;; slightly simpler ones (sort the first half, sort the second half, sort
;; all elements but one), plus some overhead processing. We continue
;; doing this recursively until the lists have at most one element each,
;; at which point we are forced to surrender.

(use srfi-1)

(define (split lst)
  (let ((half (quotient (length lst) 2)))
    (list (take lst half)
          (drop lst half))))

(define sample-list '(239 495 631 786 853 750 886 457 784 449 584 47
                          885 514 731 772 249 239 1000 731))
(define (slowsort inputlist)
  (if (null? inputlist) inputlist
      (let [(max (slowmax inputlist))]
        (reverse (cons max (reverse (slowsort (delete max inputlist))))))))

(define (slowmax inputlist)
  (if (null? (cdr inputlist))
      (car inputlist)
      (let* [(halves (split inputlist))
             (first-half (car (reverse (slowsort (car halves)))))
             (second-half (car (reverse (slowsort (cadr halves)))))]
        (if (> first-half second-half) first-half second-half))))

(slowsort sample-list)