-----------------------------------------------------------------------------
-- |
-- Module      :  QSort
-- Copyright   :  Lennart Augustsson
-- 
-- Maintainer  :  Malcolm Wallace <Malcolm.Wallace@cs.york.ac.uk>
-- Stability   :  Stable
-- Portability :  All
--
--    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