Java™ How To Program (Early Objects), Tenth Edition

19.7.2 Efficiency of the Insertion Sort

The insertion sort algorithm also runs in O(n²) time. Like selection sort, the implementation of insertion sort (lines 9–28) contains two loops. The for loop (lines 12–27) iterates data.length - 1 times, inserting an element into the appropriate position in the elements sorted so far. For the purposes of this application, data.length - 1 is equivalent to n – 1 (as data.length is the size of the array). The while loop (lines 18–23) iterates over the preceding elements in the array. In the worst case, this while loop will require n – 1 comparisons. Each individual loop runs in O(n) time. In Big O notation, nested loops mean that you must multiply the number of comparisons. For each iteration of an outer ...