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.

source

source

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

  1. For each index in the input array:
    1. Set the j variable to i.
  2. Loop while j is greater than 0 and the element at index j - 1 is greater than the element at index j:
    1. Swap the elements at index j and j - 1.
    2. Decrement j by 1.

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)

Thank you for reading! 😊