The insertion-sort algorithm provides an alternative to the selection-sort algorithm for sorting something like a hand of cards, where there is a small number of items (about 20 or less). It’s more efficient than selection sort if the array is only slightly out of order, but it’s relatively inefficient for large numbers of items. The following code implements a descending insertion-sort algorithm:

Note that the scope of the j count variable extends beyond the scope of the for loop in which it’s used. Assume that an array of int has been instantiated and the insertionSort method has been called with a reference to this array passed in as a parameter. Trace the execution of this method, using the following header and initial entries:

1 2 3 4 5 6989 7 10 11 12 13 14 15 16 public static void insertion Sort(int[] cards) { int pick; int j; for (int i=1; i 0 && pick>cards[j-1]; j--) { } cards[j] = cards[j-1]; cards[j] // pick each successive element = pick; } } // end insertion Sort // insert as next highest