title: Why is insertion sort Θ(n^2) in the average case?
body: <p><a href="http://en.wikipedia.org/wiki/Insertion_sort">Insertion sort</a> has a runtime that is &Omega;(n) (when the input is sorted) and O(n<sup>2</sup>) (when the input is reverse sorted).  On average, it runs in &Theta;(n<sup>2</sup>) time.</p>
  
  <p>Why is this?  Why isn't the average case closer to O(n log n), for example?</p>