The insertion sort

The insertion sort is a simple and popular sorting algorithm. Since it has O(n2) average runtime it is very inefficient for sorting larger datasets. However, it is an algorithm of choice when the data is nearly sorted or when the dataset is small. Given those two conditions, it can potentially outperform sorting algorithms that are O(n log(n)) time complexity, such as merge sort.

The algorithm

The insertion sort algorithm performs in-place sorting and works with any element type that conforms to the comparable protocol. The element type must conform to comparable because we need to compare the individual elements against each other. It will make N-1 iterations, where i = 1 through N-1. The algorithm leverages the fact that elements 0 through i-1 have already been put in sorted order.

Let's look at the algorithm:

1  public func insertionSort<T: Comparable>(_ list: inout [T] ) { 
2      
3      if list.count <= 1 { 
4          return 
5      } &...