content: {-
     This module implements a sort function using a variation on
     quicksort.  It is stable, uses no concatenation and compares
     only with <=.
    
     sortLe sorts with a given predicate
     sort   uses the <= method
    
     Author: Lennart Augustsson
  -}
  
  module QSort(sortLe, sort) where
  sortLe :: (a -> a -> Bool) -> [a] -> [a]
  sortLe le l = qsort le   l []
  
  sort :: (Ord a) => [a] -> [a]
  sort      l = qsort (<=) l []
  
  -- qsort is stable and does not concatenate.
  qsort le []     r = r
  qsort le [x]    r = x:r
  qsort le (x:xs) r = qpart le x xs [] [] r
  
  -- qpart partitions and sorts the sublists
  qpart le x [] rlt rge r =
      -- rlt and rge are in reverse order and must be sorted with an
      -- anti-stable sorting
      rqsort le rlt (x:rqsort le rge r)
  qpart le x (y:ys) rlt rge r =
      if le x y then
  	qpart le x ys rlt (y:rge) r
      else
  	qpart le x ys (y:rlt) rge r
  
  -- rqsort is as qsort but anti-stable, i.e. reverses equal elements
  rqsort le []     r = r
  rqsort le [x]    r = x:r
  rqsort le (x:xs) r = rqpart le x xs [] [] r
  
  rqpart le x [] rle rgt r =
      qsort le rle (x:qsort le rgt r)
  rqpart le x (y:ys) rle rgt r =
      if le y x then
  	rqpart le x ys (y:rle) rgt r
      else
  	rqpart le x ys rle (y:rgt) r
  
  