3-4 Insertion Sort

A. Notes Insertion Sort is yet another sorting algorithm. Steps to sort an array ascending are below.

Step 1 − If it is the first element, it is already sorted. return 1;
Step 2 − Pick next element
Step 3 − Compare with all elements in the sorted sub-list
Step 4 − Shift right all the elements in the sorted sub-list that is greater than the value to be sorted
Step 5 − Insert the value
Step 6 − Repeat until list is sorted

To sort an array descending, just change "greater than" to "less than" when comparing.

Step 1 − If it is the first element, it is already sorted. return 1;
Step 2 − Pick next element
Step 3 − Compare with all elements in the sorted sub-list
Step 4 − Shift right all the elements in the sorted sub-list that is less than the value to be sorted
Step 5 − Insert the value
Step 6 − Repeat until list is sorted

B. Watch

A good example of step by step sorting process is here. This YouTube video is only 2 minutes, but very helpful.

C. HW: Practice insertion sort algorithm on paper to sort the array below. After 5 comparisons and insertions, what will the array look like? {30099,181263,10128,5238,3839,5170,5641,11000,15973,1200,12500,87337,107430,227931,56400}