Terence Xie :
Introduction to algorithms gives the details of insertion sort in chapter 2.1, which discuss the whole process of insertion sort.\n\nThe worst case is caused by the switch of subarray in reversed order.",
2012-06-23T13:21:19
amit :
\nThe run time is not n(n-1)/2, each step requires more then 1\nmachine OP (in all machine I am aware of). This is why we usually\nuse big O notation and \"ignoring\" constants in algorithms\nanalysis - we want to make our analysis generic and platform\nindependent.\nInsertion sort is analyzed as n(n-1)/2 = O(n^2) because it is\nsum of arithmetic progression. The first iteration requires 1\nstep, the second 2 steps,.. the n'th requires n steps, so we get 1 + 2 + ... + n = n(n-1)/2 from sum of arithmetic progression.\n",
2012-06-23T08:17:47