Knowledge Base > Algorithm > Sorting
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.
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,
At the start of each jth iteration, the subarray A[1…j - 1] consists of the elements originally in A[1…j - 1], but in sorted order.
Before the 1st iteration, while j = 2. The subarray A[1…j - 1] → A is in fact the original element in A, and is in an sorted order.
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 ith iteration.
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.
Hence, the worst running time, in the case of a reversed order list, is T(n) = c1 ⋅ (n) + c2 ⋅ = O(n2), where O(n2) 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.
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).
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