Insertion Sort (idea)

Insertion sort will sort a field of n numbers in the worst case scenario in O(n²) time. In the best case scenario, however, it will sort a field of n numerbers in O(n) time. The best case scenario is when the field is already sorted or almost sorted. This is important to remember and this property of insertion sort makes it a very usefull algorithm for a number of different problems.

A more accurate way to state the effiency of insertion sort is to say that it is both Ω(n) and O(n²).

---

This is an implementation of insertion sort in haskell:

ins x [] = [x]
ins x lst@(y:ys)
  | (x < y)   = x:(lst)
  | otherwise = y:(ins x ys)

isort [] = []
isort (x:xs) = ins x (isort xs)