The Insertion Sort

The Algorithm
- Consider the list to be in two parts.
  - The first part is sorted.
  - The second part is unsorted.
- Initially, element 0 is in the sorted part and elements 1 through n − 1 are in the unsorted part.
- Make n − 1 passes over the list. Number the passes 1 to n − 1.
- On pass k,
  - Insert element k into the sorted part (elements 0 through k − 1).
The Insertion Sort has a run time of order n².
Example - InsertionSort.cpp.

Return to Lectures page

This page was last modified on Apr 23, 2001

URL: http://people.hsc.edu/faculty-staff/robbk/Coms262/Lectures/InsertionSort.html