-- Implementation of insertion sort

module ISort
where

import Debug.Trace

-- Insert an element into a sorted list so that the result is still sorted
--
-- Example: insertSorted 7 [2, 4, 6, 9] = [2,4,6,7,9]
--
insertSorted :: Ord a => a -> [a] -> [a]
insertSorted e []     = [e]
insertSorted e (x:xs)
  | e < x             = e : x : xs
  | otherwise         = x : insertSorted e xs

traceInsertSorted e xs = 
  let result = insertSorted e xs
      msg    = "insertSorted " ++ show e ++ " " ++ show xs ++ 
	       " = " ++ show result
  in
  trace msg result

-- Sort a list using the insertion sort algorithm
--
-- Example: isort [7, 9, 2, 6, 4] = [2,4,6,7,9]
--
isort :: (Show a, Ord a) => [a] -> [a]
isort []     = []
isort (x:xs) = trace ("Inserting " ++ show x) (traceInsertSorted x (isort xs))