insertion sort

Insertion sort is a sorting algorithm that sorts by dividing the original array into two regions: sorted and unsorted. For each unsorted element beginning at the left, we try to find a place in the sorted region where we can place the element. The element is put back to the correct location by continuously swapping it with the element to the left until the left element is equal or less (or if there is no more element to the left).

Analysis

Worst-case time complexity: $O(n^2)$

• Intuition: In the worst case (i.e. the array is in descending order when we trying to sort it in ascending order), every unsorted element has to be swapped with all sorted elements to the left until it reaches the leftmost position. That would be equivalent to $O(\frac{n(n+1)}{2})=O(n^2)$.

Implementation

Pseudocode from Wikipedia:

i ← 1
while i < length(A)
    j ← i
    while j > 0 and A[j-1] > A[j]
        swap A[j] and A[j-1]
        j ← j - 1
    end while
    i ← i + 1
end while

• We start at i = 1 because the first element (if it exists) on its own is already sorted.
• We iterate from i = 1 to the end of the array A. This outer loop sorts the element at i.
• The inner loop iterates from j = i backwards.
  • If the element to the left (the previous element) is greater than the current one, we swap the two to put them in order.
  • When the previous element is not greater, then the current element is in its proper place.