example consider an array of integers given below we will sort the values in the array using insertion sort solution ais the only element in sorted list (pass (pass (pass (pass (pass sorted (pass (pass (pass (pass unsorted initiallya[ is the only element in the sorted set in pass [ will be placed either before or after [ ]so that the array is sorted in pass [ will be placed either before [ ]in between [ and [ ]or after [ in pass [ will be placed in its proper place in pass - [ - will be placed in its proper place to keep the array sorted to insert an element [kin sorted list [ [ [ - we need to compare [kwith [ - ]then with [ - ] [ - ]and so on until we meet an element [jsuch that [ < [kin order to insert [kin its correct positionwe need to move elements [ - insertion-sort (arrna[ - ] [jby one position and then [kis step repeat steps to for to inserted at the ( + )th location the algorithm for step set temp arr[kinsertion sort is given in fig step set in the algorithmstep executes for step repeat while temp <arr[jset arr[ arr[jloop which will be repeated for each element in set the array in step we store the value of the kth [end of inner loopelement in temp in step we set the jth index step set arr[ temp in the array in step for loop is executed [end of loopstep exit that will create space for the new element from figure algorithm for insertion sort the unsorted list to be stored in the list of sorted elements finallyin step the element is stored at the ( + )th location complexity of insertion sort for insertion sortthe best case occurs when the array is already sorted in this casethe running time of the algorithm has linear running time ( ( )this is becauseduring each iterationthe first element from the unsorted set is compared only with the last element of the sorted set of the array similarlythe worst case of the insertion sort algorithm occurs when the array is sorted in the reverse order in the worst casethe first element of the unsorted set has to be compared with almost every element in the sorted set furthermoreevery iteration of the inner loop will have to shift the elements of the sorted set of the array before inserting the next element thereforein the worst caseinsertion sort has quadratic running time ( ( )even in the average casethe insertion sort algorithm will have to make at least ( - )/ comparisons thusthe average case also has quadratic running time