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:

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/
```
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
Math Forum Home || Math Library || Quick Reference || Math Forum Search