Week 03 (Sorting) (26)

Cost analysis (where n = hi-lo+1):

cost for i ^th iteration:
- n-i comparisons, ?? swaps
- S depends on "sortedness", best=0, worst=n-i
how many iterations? depends on data orderedness
- best case: 1 iteration, worst case: n-1 iterations
Cost_best = n (data already sorted)
Cost_worst = n-1 + ... + 1 (reverse sorted)
Complexity is thus O(n²)