invariants in the insertion sort at the end of each passfollowing the insertion of the item from tempthe data items with smaller indices than outer are partially sorted efficiency of the insertion sort how many comparisons and copies does this algorithm requireon the first passit compares maximum of one item on the second passit' maximum of two itemsand so onup to maximum of - comparisons on the last pass this is - *( - )/ howeverbecause on each pass an average of only half of the maximum number of items are actually compared before the insertion point is foundwe can divide by which gives *( - )/ the number of copies is approximately the same as the number of comparisons howevera copy isn' as time-consuming as swapso for random data this algorithm runs twice as fast as the bubble sort and faster than the selection sort in any caselike the other sort routines in this the insertion sort runs in ( time for random data for data that is already sorted or almost sortedthe insertion sort does much better when data is in orderthe condition in the while loop is never trueso it becomes simple statement in the outer loopwhich executes - times in this case the algorithm runs in (ntime if the data is almost sortedinsertion sort runs in almost (ntimewhich makes it simple and efficient way to order file that is only slightly out of order howeverfor data arranged in inverse sorted orderevery possible comparison and shift is carried outso the insertion sort runs no faster than the bubble sort you can check this using the reverse-sorted data option (toggled with newin the insertsort workshop applet sorting objects for simplicity we've applied the sorting algorithms we've looked at thus far to primitive data typelong howeversorting routines will more likely be applied to objects than primitive types accordinglywe show java program in listing objectsort javathat sorts an array of person objects (last seen in the classdataarray java program in