Insertion Sort

Insertion Sort is a simple sorting algorithm. It is like picking up an element from the list and inserting it to its rightful index as per intendent order of the elements in the list. Initially, the first element is considered to be at its right place and as we go through the elements of the list, the sorting takes place by comparing the elements.

Illustration:

Algorithm:

for all elements in list,step=from step=0 to step=length(list)-1

    first element is sorted,when step=0

    key=list[step],the element to be extracted to insert at the right index

    j=step-1

    while j>=0 and key < value at index j

        list[j+1]=list[j]

        j=j-1

    list[j+1]=key

Time Complexity:

• Worst Case: O(n²)
• Average Case: O(n²)
• Best Case: O(n)

Space Complexity: O(1)

Program for insertion sort:

Output: