being taken to remember [ first!)and then we can move the old [ to [ ]giving at the next stepthe algorithm treats [ ], [ as an already sorted array and tries to insert [ ]= this value obviously has to fit between [ ]= and [ ]= this is achieved by moving [ 'upone slot to [ (the value of which we assume we have remembered)allowing us to move the current value into [ ]giving finallya[ ]= has to be inserted into the sorted array [ ], [ since [ ]= is bigger than it is moved 'upone slotand the same happens for [ ]= comparison with [ ]= shows that [ was the slot we were looking forgiving the general algorithm for insertion sort can therefore be writtenfor +forj -if [ja[ - swap [jand [ - else break the outer loop goes over the items to be insertedand the inner loop takes each next item and swaps it back through the currently sorted portion till it reaches its correct position howeverthis typically involves swapping each next item many times to get it into its right positionso it is more efficient to store each next item in temporary variable and only insert it into its correct position when that has been found and its content movedfor + [jwhile & [ - [ja[ - - [jt the outer loop again goes over - itemsand the inner loop goes back through the currently sorted portion till it finds the correct position for the next item to be inserted the time complexity is again taken to be the number of comparisons performed the outer loop is always carried out times how many times the inner loop is carried out depends on the items being sorted in the worst caseit will be carried out timeson averageit will be half that often hence the number of comparison in the worst case isn- xx = = - = ( (