332. Insertion Sort

What is Insertion Sort??

1. Insertion sort is a simple sorting algorithm that builds the sorted array one item at a time.
2. Efficient for small data sets, not efficient for large data sets.
3. Most of the time we sort the playing cards in our hand using insertion sort without knowing about it.
4. At any given time, your array will be partially sorted and partially unsorted. At the end, you will have fully sorted array.
5. In every iteration, one element will be taken from unsorted array and placed at its right position in the sorted array. Iteration ends when there are no elements left in the unsorted array.

Pseudo Code:

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

See the video below for more understanding.

Time Complexity: O(N²)

Output:

Original Array: [5, 1, 9, 3, 2, 10]
(Insertion Sort)- Sorted Array: [1, 2, 3, 5, 9, 10]

Reference: Wiki