# 1. Introduction

*Insertion Sort* is a simple sorting algorithm that works similarly to how one sorts playing cards in their hands. It builds the final sorted array one item at a time. It's generally used when the number of elements is small or when the input array is almost sorted, and only a few elements are misplaced.

# 2. Implementation Steps

1. Start from the second element (assume the first element is sorted).

2. Compare the current element with the previous element.

3. If the current element is smaller than the previous element, compare it with the elements before until an element smaller than it is found or until the start of the array is reached.

4. Place the current element in its correct position so that the elements before are smaller than the current element.

5. Repeat the above steps for all the elements in the array.

# 3. Implementation in Swift

```
func insertionSort(_ array: inout [Int]) {
for i in 1..<array.count {
// 1. Start from the second element
let key = array[i]
var j = i - 1
// 2. Compare the current element with the previous element
while j >= 0 && array[j] > key {
// 3. If current element is smaller, compare with elements before it
array[j + 1] = array[j]
j = j - 1
}
// 4. Place the current element in its correct position
array[j + 1] = key
}
}
// Usage:
var numbers = [64, 34, 25, 12, 22, 11, 90]
insertionSort(&numbers)
print(numbers)
```

### Output:

[11, 12, 22, 25, 34, 64, 90]

### Explanation:

1. We start by iterating from the second element of the list (assuming the first element is already sorted).

2. For each iteration, we store the current element in a variable *key*. We then compare this *key* with the previous elements.

3. If the *key* is smaller than the previous element, we shift the previous element to the right. We continue shifting elements until we find the correct position for the *key* or until we reach the start of the list.

4. We then place the *key* in its correct position such that elements to the left are smaller and elements to the right are larger.

5. This process is repeated for every element in the array, resulting in a sorted list at the end.