Insertion Sort — Swift

Insertion sort is an In Place sorting algroithm and is similar to how most people arrange a hand of poker cards.

1. Start with one card in your hand.
2. Pick the next card and insert it into its proper sorted order.
3. Repeat previous step for all cards.

func insertionSort<T: Comparable>(_ nums: inout [T]) {
    if nums.isEmpty {
        return
    }
    for i in 1..<nums.count {
        let value = nums[i]
        var j = i - 1
   
        while j >= 0 && nums[j] > value {
            nums[j + 1] = nums[j]
            j -= 1
        }
    
        nums[j + 1] = value
    }
}
var array = [40, 13, 20, 8]
insertionSort(&array)

Complexity Analysis

The outer loop executes N−1 times, that’s quite clear. But the number of times the inner-loop is executed depends on the input:

1. In best-case scenario, the array is already sorted and (a[j] > X) is always false
   So no shifting of data is necessary and the inner loop runs in O(1),
2. In worst-case scenario, the array is reverse sorted and (a[j] > X) is always true
   Insertion always occur at the front of the array and the inner loop runs in O(N).

Thus, the best-case time is O(N × 1) = O(N) and the worst-case time is O(N × N) = O(N²).