ghc/lib/hbc/QSort.hs

   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