chap internal sorting = figure an illustration of insertion sort each column shows the array after the iteration with the indicated value of in the outer for loop values above the line in each column have been sorted arrows indicate the upward motions of records through the array insertion sort imagine that you have stack of phone bills from the past two years and that you wish to organize them by date fairly natural way to do this might be to look at the first two bills and put them in order then take the third bill and put it into the right order with respect to the first twoand so on as you take each billyou would add it to the sorted pile that you have already made this naturally intuitive process is the inspiration for our first sorting algorithmcalled insertion sort insertion sort iterates through list of records each record is inserted in turn at the correct position within sorted list composed of those records already processed the following is java implementation the input is an array of records stored in array static void sort( [afor (int = < lengthi++/insert 'th record for (int = ( > &( [jcompareto( [ - ])< ) --dsutil swap(ajj- )consider the case where inssort is processing the ith recordwhich has key value the record is moved upward in the array as long as is less than the key value immediately above it as soon as key value less than or equal to is encounteredinssort is done with that record because all records above it in the array must have smaller keys figure illustrates how insertion sort works the body of inssort is made up of two nested for loops the outer for loop is executed times the inner for loop is harder to analyze because the number of times it executes depends on how many keys in positions to have value less than that of the key in position in the worst caseeach record