Introduction
The insertion sort algorithm builds a sorted list one item at a time by comparison. It is more efficient on small datasets but much less efficient on larger ones.
Code Example
func insertionSort(_ array: [Int]) -> [Int] {
var A = array
for i in 0 ..< A.count {
var j = i
while j > 0 && A[j - 1] > A[j] {
let tmp = A[j]
A[j] = A[j - 1]
A[j - 1] = tmp
j -= 1
}
}
return A
}
Implementation
- For each index in the input array:
- Set the
j
variable toi
.
- Set the
- Loop while
j
is greater than0
and the element at indexj - 1
is greater than the element at indexj
:- Swap the elements at index
j
andj - 1
. - Decrement
j
by 1.
- Swap the elements at index
Why use Insertion Sort?
- Fast for small data sets. More efficient in practice than most other algorithms, such as selection sort or bubble sort.
- Adaptive: Efficient for datasets that are already substantially sorted; the time complexity is O(kn) when each element in the input is no more than k places away from its sorted position.
- Stable: Does not change the relative order of elements with equal keys.
- In-place: Only requires O(1) of additional memory space.
- Online: Can sort a list as it receives it.
Time/Space Complexity
- Time: O(N^2)
- Space: O(1) (in-place)