Comparison between 2 naive sorting algorithms in Haskell

haskell-lists.hs

-- sort1 and sort2 finds the smaller number of a list
-- and concatenates with the sorted list of the remaining
-- items of a list (recursively)

-- it keeps removing the head and operating on the rest of the list
-- recursivelly until it can unstack while concatenating the
-- smaller items to the left of the list to be returned


-- sorting a list using the worse approach
-- with recursive function calls used in the conditional part of guards
smaller [a] = a
smaller (a:c)
  | a < (smaller c) = a
  | otherwise = smaller c

remove_smaller [a] = []
remove_smaller (a:c)
  | a == smaller (a:c) = c
  | otherwise = a : remove_smaller c

sort1 [] = []
sort1 [a] = [a]
sort1 l = (smaller l) : sort1 (remove_smaller l)

-- sort the list using a "smarter" approach
smaller2 [a] = a
smaller2 [a,b]
  | a < b = a
  | otherwise = b
smaller2 (a:b:c)
  | a < b = smaller2 (a:c)
  | otherwise = smaller2 (b:c)

remove2 _ [] = []
remove2 m [a]
  | m == a = []
  | otherwise = error "o smaller valor nao esta na lista"
remove2 m (b:c)
  | m == b = c
  | otherwise = b : remove2 m c

sort2 [] = []
sort2 [a] = [a]
sort2 l = (smaller2 l) : sort2 (remove2 (smaller2 l) l)