+
+%-----------------------------------------------------------------------------
+Quick Sort algorithm taken from HBC's QSort library.
+
+\begin{code}
+sort :: (Ord a) => [a] -> [a]
+sortBy :: (a -> a -> Ordering) -> [a] -> [a]
+
+#ifdef USE_REPORT_PRELUDE
+sort = sortBy compare
+sortBy cmp = foldr (insertBy cmp) []
+#else
+
+sortBy cmp l = qsort cmp l []
+sort l = qsort compare l []
+
+-- rest is not exported:
+
+-- qsort is stable and does not concatenate.
+qsort cmp [] r = r
+qsort cmp [x] r = x:r
+qsort cmp (x:xs) r = qpart cmp x xs [] [] r
+
+-- qpart partitions and sorts the sublists
+qpart cmp x [] rlt rge r =
+ -- rlt and rge are in reverse order and must be sorted with an
+ -- anti-stable sorting
+ rqsort cmp rlt (x:rqsort cmp rge r)
+qpart cmp x (y:ys) rlt rge r =
+ case cmp x y of
+ GT -> qpart cmp x ys (y:rlt) rge r
+ _ -> qpart cmp x ys rlt (y:rge) r
+
+-- rqsort is as qsort but anti-stable, i.e. reverses equal elements
+rqsort cmp [] r = r
+rqsort cmp [x] r = x:r
+rqsort cmp (x:xs) r = rqpart cmp x xs [] [] r
+
+rqpart cmp x [] rle rgt r =
+ qsort cmp rle (x:qsort cmp rgt r)
+rqpart cmp x (y:ys) rle rgt r =
+ case cmp y x of
+ GT -> rqpart cmp x ys rle (y:rgt) r
+ _ -> rqpart cmp x ys (y:rle) rgt r
+
+#endif /* USE_REPORT_PRELUDE */
+\end{code}