Segment list into two halves. The first half is the sorted section. The second half is the unsorted section. Take the first element in the unsorted section and move it to the end of the sorted section. Continually compare to the adjacent element and swap if the condition of order isn’t met. The algorithm ends when there are no elements left in the unsorted section.
Quick Facts
- A comparison sorting algorithm.
- Fast on lists that are mostly sorted. \(O(n)\)
- Slow on lists that are completely unsorted \([3, 2, 1, 0]\). Quadratic time. \(O(n^2)\)
- In place sorting algorithm. Consumed space \(O(1)\).
func insertionSort(_ array: inout [Int]) -> [Int] {
for i in 1 ..< array.count {
var j = i
while j > 0, array[j] < array[j - 1] {
array.swapAt(j, j - 1)
j -= 1
}
}
return array
}
