DSA by Mitul in C++, Python, and Java : Insertion Sort

Here we first divide the given array into 2 part. Then we take first element from unsorted array and find its correct position in sorted array. Finally we repeat until unsorted array is empty.

Assume we have this array:

Lets divide it into 2 parts (Sorted & Unsorted):

Now we will take the first element from the unsorted array which is 5 and place it in the sorted array:

Again we will take the 1st element from the unsorted array which is 3. We will move it to the sorted array. But for sorting, we have to compare it with element in the sorting array. And then keep it in the sorting order.

Done!

We will repeat this process until the unsorted array is empty.

Gradually we will have:

Finally , we have:

Code for Insertion sort

def insertionSort(customList):
    for i in range(1, len(customList)):
        key = customList[i]
        j = i-1
        while j>=0 and key < customList[j]:
            customList[j+1] = customList[j]
            j -= 1
        customList[j+1] = key
    return customList

Complexity Analysis

Why to use Insertion Sort?

1. When we have insufficient memory.
2. Easy to implement.
3. When we have continuous inflow of numbers and we want to keep them sorted.

Why to avoid Insertion Sort?
When time is a concern.