Insertion Sort Algorithm
Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort.
However, insertion sort provides several advantages:
1. Simple implementation: Jon Bentley shows a three-line c version, and a five-line optimized version
Efficient for (quite) small data sets, much like other quadratic sorting algorithmsAdaptive, i.e., efficient for data sets that are already substantially sorted: the time complexity is O(kn) when each component in the input is no more than K places away from its sorted position
2. Stable; i.e., makes not change the relative order of components with equal keys
/**
* This file is part of Scalacaster project, https://github.com/vkostyukov/scalacaster
* and written by Vladimir Kostyukov, http://vkostyukov.ru
*
* Insertion Sort http://en.wikipedia.org/wiki/Insertion_sort
*
* Worst - O(n^2)
* Best - O(n)
* Average - O(n^2)
*/
def insertionsort[A <% Ordered[A]](list: List[A]): List[A] = {
def sort(as: List[A], bs: List[A]): List[A] = as match {
case h :: t => sort(t, insert(h, bs))
case Nil => bs
}
def insert(a: A, as: List[A]): List[A] = as match {
case h :: t if (a > h) => h :: insert(a, t)
case _ => a :: as
}
sort(list, Nil)
}
