Running Time of an Insertion Sort

Date: 08/06/99 at 11:24:45
From: Elizabeth Thomas
Subject: Running time of an insertion sort

Here's my question:

"Insertion sort" is the procedure that sorts an array of n numbers as 
follows: Search through the entire array, find the smallest element, 
and place it in the first position in the array. Then find the 
next-smallest number, and place it in the second position of the 
array. Continue until the array is sorted.

Write and solve a recurrence formula for the running time of an 
insertion sort. Which is better, insertion sort or merge-sort?

I tried to sort A[1...n], by recursively sorting A[1...n-1] and 
inserting the final element, but I must be doing something wrong.

Thanks for your help; it is greatly appreciated.

Date: 08/07/99 at 21:52:52
From: Doctor Tom
Subject: Re: Running time of an insertion sort

Hi Elizabeth,

Here's how to do it. First, figure out what you're counting. In this 
case, let's look at the number of numbers you have to examine to 
complete the sort.

If there's only one number in the list, no work is required, so zero 
numbers need to be examined, right?

If there are two numbers in the list, you examine both to find the 
smaller (that's two examinations) but then you're done, because you 
know the other is larger. That's two total examinations.

If there are three numbers, you look at all three to find the 
smallest, and after you have that, you're still faced with an 
insertion sort of the remaining two numbers, which we know from the 
previous paragraph requires 2 more examinations: 5 total.

Et cetera. For n items, you need n examinations plus the number of 
examinations to sort n-1 items.

Here's how it looks:

      Items
     to sort   Examinations
        1         0
        2         2
        3         3+2
        4         4+3+2
        5         5+4+3+2
        :          :

For the analysis of a merge sort, let's just look at a sort of 2^n 
items.

To sort 1 item (1 = 2^0) requires zero examinations.

To sort 2^n items, you need to do 2 merge-sorts of 2^(n-1) and then 
look (at worst) at 2^n items to do the final merge sort:

      Items
     to sort    Examinations
        1       0        =  0
        2       2        =  2
        4       4 + 2*2  =  8
        8       8 + 2*8  = 24
       16      16 + 2*24 = 64
        :         :

Notice that for a merge sort this is an upper bound. If you do a merge 
and you finish one list, you don't need to look at the others in the 
list.

- Doctor Tom, The Math Forum
  http://mathforum.org/dr.math/