CMP 761: Analysis of Algorithms
Lehman College, City University of New York
Fall 2002

Notes for Lecture: Sorting
3 September 2002

Sorting Problem

Here is how we formally define the sorting problem:

Input: A sequence of n numbers (A[1],A[2],...,A[n])
Output: A permutation (reordering) (A'[1],A'[2],...,A'[n]) of the input sequence such that A'[1] <= A'[2] <= ... <= A'[n].

Insertion Sort

The pseudocode for insertion sort:
INSERTION-SORT(A)
1  for j <- 2 to length[A]
2    do key <- A[j]
3      // Insert A[j] into the sorted sequence A[1..j-1]
4      i <- j-1
5      while i > 0 and A[i] > key
6        do A[i+1] <- A[i]
7          i <- i-1
8      A[i+1] <- key

It is useful to identify properties, called loop invariants, that hold for each iteration of a loop.  For the insertion sort algorithm, we have the loop invariant:
At the start of each iteration of the for loop of lines 1-8, the subarray A[1..j-1] consists of the elements originally in A[1..j-1] but in sorted order.
To prove the algorithm is correct, we show that the loop invariant is true at: Initialization, Maintenance, and Termination (see book, p 18) for proof.

Analyzing the running time:
INSERTION-SORT(A)                             cost          times
1  for j <- 2 to length[A]                    c1            n
2    do key <- A[j]                           c2            n-1
3      // Insert A[j] into the sorted 
          sequence A[1..j-1]                  0             n-1
4      i <- j-1                               c4            n-1
5      while i > 0 and A[i] > key             c5
6        do A[i+1] <- A[i]                    c6
7          i <- i-1                           c7
8      A[i+1] <- key                          c8            n-1

The running time for lines 5-7 depend on how many times the condition for the while loop is true.