-- 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))