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.