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
package sort
/**
* This method implements the Generic Insertion Sort
*
* @param array The array to be sorted
* Sorts the array in increasing order
*
* Worst-case performance O(n^2)
* Best-case performance O(n)
* Average performance O(n^2)
* Worst-case space complexity O(1)
**/
fun <T: Comparable<T>> insertionSort(array: Array<T>) {
val size = array.size - 1
for (i in 1..size) {
val key = array[i]
var idx = i
for (j in i - 1 downTo 0) {
if (array[j].compareTo(key) > 0) {
array[j + 1] = array[j]
idx = j
}
else {
break
}
}
array[idx] = key
}
}
