1 {-
    2    This module implements a sort function using a variation on
    3    quicksort.  It is stable, uses no concatenation and compares
    4    only with <=.
    5   
    6    sortLe sorts with a given predicate
    7    sort   uses the <= method
    8   
    9    Author: Lennart Augustsson
   10 -}
   11 
   12 module QSort(sortLe, sort) where
   13 sortLe :: (a -> a -> Bool) -> [a] -> [a]
   14 sortLe le l = qsort le   l []
   15 
   16 sort :: (Ord a) => [a] -> [a]
   17 sort      l = qsort (<=) l []
   18 
   19 -- qsort is stable and does not concatenate.
   20 qsort le []     r = r
   21 qsort le [x]    r = x:r
   22 qsort le (x:xs) r = qpart le x xs [] [] r
   23 
   24 -- qpart partitions and sorts the sublists
   25 qpart le x [] rlt rge r =
   26     -- rlt and rge are in reverse order and must be sorted with an
   27     -- anti-stable sorting
   28     rqsort le rlt (x:rqsort le rge r)
   29 qpart le x (y:ys) rlt rge r =
   30     if le x y then
   31         qpart le x ys rlt (y:rge) r
   32     else
   33         qpart le x ys (y:rlt) rge r
   34 
   35 -- rqsort is as qsort but anti-stable, i.e. reverses equal elements
   36 rqsort le []     r = r
   37 rqsort le [x]    r = x:r
   38 rqsort le (x:xs) r = rqpart le x xs [] [] r
   39 
   40 rqpart le x [] rle rgt r =
   41     qsort le rle (x:qsort le rgt r)
   42 rqpart le x (y:ys) rle rgt r =
   43     if le y x then
   44         rqpart le x ys (y:rle) rgt r
   45     else
   46         rqpart le x ys rle (y:rgt) r
   47