[prev] 34 [next]

Insertion Sort (cont)

Complexity analysis ...
  • cost for inserting element into sorted list of length i
    • C=??, depends on "sortedness", best=1, worst=i
    • S=??, don't swap, just shift, but do C-1 shifts
  • always have N iterations
  • Costbest = 1 + 1 + ... + 1   (already sorted)
  • Costworst = 1 + 2 + ... + N = N*(N+1)/2   (reverse sorted)
  • Complexity is thus O(N2)