Program defines the class template
`StraightInsertionSorter<T>`.
This class simply provides an implementation for the `DoSort` routine.
`DoSort` takes one argument--a reference to an `Array<T>` instance.
The array initially contains the data to be sorted.
When the function returns,
the contents of the array are sorted.

**Program:** `StraightInsertionSorter<T>` Class `DoSort` Member Function Definition

In order to determine the running time
of the `DoSort` routine given in Program ,
we need to determine the number of iterations of the inner loop (lines 12-14).
The number of iterations of the inner loop
in the iteration of the outer loop
depends on the positions of the values in the array.
In the best case, the value in position *i* of the array
is larger than that in position *i*-1
and zero iterations of the inner loop are done.
In this case, the running time for insertion sort is *O*(*n*).
Notice that the best case performance occurs
when we sort an array that is already sorted!

In the worst case, *i* iterations of the inner loop are required
in the iteration of the outer loop.
This occurs when the value in position *i* of the array is smaller
than the values at positions 0 through *i*-1.
Therefore, the worst case arises when we sort an array in which the elements
are initially sorted in reverse.
In this case the running time for insertion sort is .

Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.