Example
Quicksort is a common sorting algorithm with an average case complexity of O(n log n) and a worst case complexity of O(n^2). Its advantage over other O(n log n) methods is that it can be executed in-place.
Quicksort splits the input on a chosen pivot value, separating the list into those values that are less than and those values that are greater than (or equal to) the pivot. Splitting the list is easily done with filter.
Using this, a Scheme implementation of Quicksort may look like the following:
(define (quicksort lst)
(cond
((or (null? lst) ; empty list is sorted
(null? (cdr lst))) ; single-element list is sorted
lst)
(else
(let ((pivot (car lst)) ; Select the first element as the pivot
(rest (cdr lst)))
(append
(quicksort ; Recursively sort the list of smaller values
(filter (lambda (x) (< x pivot)) rest)) ; Select the smaller values
(list pivot) ; Add the pivot in the middle
(quicksort ; Recursively sort the list of larger values
(filter (lambda (x) (>= x pivot)) rest))))))) ; Select the larger and equal values
