Insertion Sort

⚠️ This post was created when I was in high school and is no longer maintained.

1. Pseudocode

-- Interactive version --
algorithm InsertionSort(array, n):
    For j := 2 to n do
        key := array[j]
        i := j - 1
        while i > 0 and array[i] > key:
            array[i] = array[i+1]
            i -= 1
        arrary[i+1] = key

-- Recursive version --
algorithm InsertionRec(A): --> A == array
    InsertionRecAux(A, A.length) --> arbitrarily take the last element as the key 

algorithm InsertionRecAux(A, keyIndex):
    if keyIndex <= 1 then 
        return
    InsertionRecAux(A, keyIndex-1) 
    Insert(A, keyIndex) 

algorithm Insert(A, keyIndex):
    key := A[keyIndex]
    i := keyIndex - 1
    While i > 0 and A[i] > key do
        A[i+1] = A[i]
        i -= 1
    A[i+1] := key

Remark on the recursive version:

• In the Insert() phase, we assume that the input-array A is already sorted. This is because we recursively call InsertionRecAux() and the call-stack only bounces back (return) when it hits the base case, which is, in this case, when keyIndex <= 1.
• When we start inserting, therefore, the index of the key starts from 1 (one element per se is sorted)
• In other words, we do recursion first and only start inserting when recursion stack bounces back.

---

2. Time cmplexity

(1) Upper bound

\(T(n) = for + for \cdot while \approx c_0\cdot n + c_1\cdot\textstyle\sum_2^n(j-1)\) \(T(n) \in O(n^2)\)

(2) Θ and O

Worst-case time complexity of insertion sort is in

\(O(n^2)\space or\space \Theta(n^2)\) but the time complexity of insertion sort is in \(O(n^2)\) but NOT in \(Θ(n^2)\) Recall the definiation of Theta and O()

the best-case of insertion sort \(Θ(n^2)\)

---

$ Worst-case in-depth analysis

where I(n) gives the running time for inserting an element (‘the nth element’) in a sorted array of length (n − 1). Inserting an element at the right position in a sorted array of length (n − 1) takes in the worst-case order n steps because then we have to traverse the complete array. So I(n) = c1 · n + c2 for some constants c1 and c2. Hence we find for the recurrence equation for T the following:

Using the substitution method we find:

We hit the base case when n − i = 1, that is, i = n − 1. We then substitute and find:

Hence, T(n) is in Theta(n^2^)

Tips: Compared with marge sort, for insertion sort, we have a recursive call on the array with only one element remains.

---

3. Space complexity

Insertion sort is an in-place sorting algorithm.

---

4. Code

# python:
def InsertionSort(array, n):
    for j in range(n):
        key = array[j]
        i = j - 1
        while i >= 0 and array[i] > key:
            array[i+1] = array[i]
            i -= 1
        array[i+1]  = key

if __name__ == "__main__":
    array = [4234,234234,23,234,-134,4123,41,578,-342,55,0.2323,0.325]
    print("\nBefore sorting:", array)
    InsertionSort(array, len(array))
    print("\nAfter sorting:", array)

// Scala:
object InsersionSortAlgo {

    def InsersionSort(array: Array[Double], n: Int): Array[Double] = {
        for (j <- 1 until n) {
            var key: Double = array(j)
            var i: Int = j - 1
            while (i >= 0 && array(i) > key) {
                array(i+1) = array(i)
                i -= 1
            }
            array(i+1) = key
        } 
        array
    }

    def main(args:Array[String]): Unit = {
        var array = Array(4234,234234,23,234,-134,4123,41,578,-342,55,0.2323,0.325)
        println("\nBefore sorting:")
        println(array.deep.mkString(" "))
        println("\nAfter sorting:")
        println(InsersionSort(array, array.length).deep.mkString(" "))
    } 
}