Insertion Sort

# Approach Assume two part of the array sorted & unsorted. Sorted start from 1 element A[0] & fills with unsorted one by one (A[1] to A[n-1]) Attached code with dry run.

// Insertion Sort
// TC: O(n^2) worst . O(n). Best
// SC: O(1)
func insertionSort(_ arr: inout [Int]) {
    
    for i in 1..<arr.count {
        var current = arr[i]
        var j = i - 1
        while j >= 0 && arr[j] > current {
            arr[j + 1] = arr[j]
            j -= 1
        }
        arr[j + 1] = current
       // print("arr-->", arr, j)
    }
}


var arrayToSort: [Int] = [5,4,10,1,6,2]
insertionSort(&arrayToSort)
print("Sorted Array--> ", arrayToSort) // [1, 2, 4, 5, 6, 10]

 In Insertion sort we sort using two sets. One is Sorted set Another is unsorted one. Initially we sorted is index 0 element & rest is unsorted set. Now we move forward one by one with unsorted array & compare element & pick element from unsorted to sorted one At the right place.<While finding the right place we swap element using inner while loop>