3.9.3 Insertion Sort

Knowledge Base > Algorithm > Sorting

Overview

Insertion Sort is a comparison based sort, which sorts the array one entry at a time. This sorting algorithm is not as efficient as Quick Sort, Heap Sort, or Merge Sort. Nevertheless, it is simple to implement, perform good efficiency on small list.

Algorithm

Pseudocode

Insertion-Sort(A)

1 for j ← 2 to length[A] 2 do key ← A[j] 3         ⊴ Insert A[j] into the sorted sequence A[1..j - 1]. 4       i ← j - 1 5       while i > 0 and A[i] > key 6       do A[i + 1] ← A[i] 7             i ← i - 1 8       A[i + 1] ← key

For each iteration of an insertion sort, an element from the un-sorted data is inserted at the correct position in the sorted list until no elements are left in the un-sorted input. That is,

Loop Invariant
Statement
At the start of each j^th iteration, the subarray A[1…j - 1] consists of the elements originally in A[1…j - 1], but in sorted order.
Initialization
Before the 1^st iteration, while j = 2. The subarray A[1…j - 1] → A[1] is in fact the original element in A[1], and is in an sorted order.
Maintenance
The body of the outer FOR loop works by moving A[j - 1,j - 2,j - 3], and so on by one position to the right until the proper position for A[j] is found in lines 4-7, at which A[j] is inserted (line 8).
Before (j - 1)^th iteration, the subarray A[1…j - 2] is sorted and has the elements originally in the subarray. Now we bring in A[j - 1]. Through the algorithm, we only deal with A[j - 1] and elements in A[1…j - 2]. Hence, the elements are the one originally in A[1…j - 1].
At the end of WHILE loop for the iteration, we know A[i] ≤ A[i + 1] ≤ A[i + 2] holds, since A[i + 1] ← A[i], A[i] ≤ A[i + 2], then we previously sorted → A[i + 1] ≤ A[i + 2].
At the end of the iteration, we insert A[j - 1] → key in A[i + 1]. Again, A[i] ≤ A[i + 1] ≤ A[i + 2], since at the last round of WHILE loop, we knows A[i] > key and A[i + 1] ← A[i] and A[i + 1 - 1] ← key.
Thus, the subarray A[1…j - 1] holds for containing the originally subarray did and being sorted. By induction, A[1…j] holds at the end of i^th iteration.
Termination
The FOR loop ends when j ≥ n + 1. Substituting j = n + 1, we have subarray A[1…n] consists of original elements as in A[1…n], and in sorted order.

Thus, prove the correctness of Insertion-Sort.

Time Complexity

Hence, the worst running time, in the case of a reversed order list, is T(n) = c₁ ⋅ (n) + c₂ ⋅ = O(n²), where O(n²) of comparisons and O(n) of swaps are performed. The best case occurs if the array is already sorted. Thus, the best-case running time is T(n) = O(n), a linear function. Data movement in insertion sort depends on shifting, rather than swapping over elements.

Space Complexity

This is an in-place algorithm, which means no more than constant space is required to perform the operation. Thus, the space complexity is O(1).

Stability

After comparison, this method insert the current element A[i] into a right position in sorted list.This preserve the same order of occurrence for two duplicated elements, after the list is sorted. However, if the relational test include equality relation, this method is no longer stable

Source Code

• Insertion Sort (C)