When is Insertion Sort a good choice for sorting an array?

The array has only a few records out of sorted order
  • Each record requires a large amount of memory
  • Each record requires a small amount of memory
  • The processor speed is fast
  • The array contains many records
  • None of these situations
  • We need a reasonably fast algorithm with a good worst case

Remember that insertion sort implementation is made up of two nested for loops.

The outer for loop is executed n-1 times. While the number of times the inner for loop executes depends on how many keys in positions 0 to i-1 have a value less than that of the key in position i.