43. Insertion Sort Complexity

• It is known that for a list of length n, on average, the insertion sort makes

  • (n² + 3n – 4) / 4

  key comparisons and about

  • n(n – 1) / 4

  item assignments.

• Therefore, if

  • n = 1000,

  then to sort the list, the insertion sort makes about 250,000 key comparisons and about 250,000 item assignments.