Algorithm for Insertion Sort
Step 1: Repeat Steps 2 to 5 forK=1toN–1
Step 2: SET TEMP = ARR[K]
Step 3: SETJ=K-1
Step 4: Repeat while TEMP <= ARR[J]
SET ARR[J + 1] = ARR[J]
SETJ=J-1
[END OF INNER LOOP]
Step 5: SET ARR[J + 1] = TEMP
[END OF LOOP]
Step 6: EXIT
Explanation
- Step 1 executes a for loop which will be repeated for each element in the array.
- Step 2, we store the value of the Kth element in TEMP.
- Step 3, we set the Jth index in the array.
- Step 4, a for loop is executed that will create space for the new element from the unsorted list to be stored in the list of sorted elements.
- Step 5, the element is stored at the (J+1)th location.