content: 
  ---------------------------------------------------------------------------
  ---------------------------  Official GHC Sort ----------------------------
  ---------------------------------------------------------------------------
  
  sort1 = sortBy1 compare
  sortBy1 cmp = mergeAll . sequences
    where
      sequences (a:b:xs)
        | a `cmp` b == GT = descending b [a]  xs
        | otherwise       = ascending  b (a:) xs
      sequences xs = [xs]
  
      descending a as (b:bs)
        | a `cmp` b == GT = descending b (a:as) bs
      descending a as bs  = (a:as): sequences bs
  
      ascending a as (b:bs)
        | a `cmp` b /= GT = ascending b (\ys -> as (a:ys)) bs
      ascending a as bs   = as [a]: sequences bs
  
      mergeAll [x] = x
      mergeAll xs  = mergeAll (mergePairs xs)
  
      mergePairs (a:b:xs) = merge a b: mergePairs xs
      mergePairs xs       = xs
  
      merge as@(a:as') bs@(b:bs')
        | a `cmp` b == GT = b:merge as  bs'
        | otherwise       = a:merge as' bs
      merge [] bs         = bs
      merge as []         = as
  
  ---------------------------------------------------------------------------
  ------------------- Mergesort ---------------------------------------------
  ---------------------------------------------------------------------------
  
  sort2 l = mergesort compare l
  sortBy2 cmp l = mergesort cmp l
  
  mergesort :: (a -> a -> Ordering) -> [a] -> [a]
  mergesort cmp = mergesort' cmp . map wrap
  
  mergesort' :: (a -> a -> Ordering) -> [[a]] -> [a]
  mergesort' _   [] = []
  mergesort' _   [xs] = xs
  mergesort' cmp xss = mergesort' cmp (merge_pairs cmp xss)
  
  merge_pairs :: (a -> a -> Ordering) -> [[a]] -> [[a]]
  merge_pairs _   [] = []
  merge_pairs _   [xs] = [xs]
  merge_pairs cmp (xs:ys:xss) = merge cmp xs ys : merge_pairs cmp xss
  
  merge :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
  merge _   [] ys = ys
  merge _   xs [] = xs
  merge cmp (x:xs) (y:ys)
   = case x `cmp` y of
          GT -> y : merge cmp (x:xs)   ys
          _  -> x : merge cmp    xs (y:ys)
  
  wrap :: a -> [a]
  wrap x = [x]
  
  ----------------------------------------------------------------------
  -------------------- QuickSort ---------------------------------------
  ----------------------------------------------------------------------
  
  sort3 = qsort compare
  
  -- qsort is stable and does not concatenate.
  qsort :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
  qsort _   []     r = r
  qsort _   [x]    r = x:r
  qsort cmp (x:xs) r = qpart cmp x xs [] [] r
  
  -- qpart partitions and sorts the sublists
  qpart :: (a -> a -> Ordering) -> a -> [a] -> [a] -> [a] -> [a] -> [a]
  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 :: (a -> a -> Ordering) -> [a] -> [a] -> [a]
  rqsort _   []     r = r
  rqsort _   [x]    r = x:r
  rqsort cmp (x:xs) r = rqpart cmp x xs [] [] r
  
  rqpart :: (a -> a -> Ordering) -> a -> [a] -> [a] -> [a] -> [a] -> [a]
  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
  
  