The Math Forum

Ask Dr. Math - Questions and Answers from our Archives
Associated Topics || Dr. Math Home || Search Dr. Math

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:

     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 

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:

     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 

- Doctor Tom, The Math Forum   
Associated Topics:
High School Number Theory

Search the Dr. Math Library:

Find items containing (put spaces between keywords):
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.