JMU
Insertion Sort
An Introduction with Examples


Prof. David Bernstein
James Madison University

Computer Science Department
bernstdh@jmu.edu


Motivation
Insertion Sort
A Pseudcode Implementation
    insertionsort(a[])
    {
      for all i {

        move all elements larger than a[i] one position;
        put a[i] in the resulting "hole";
      }
    }
  
An Example
An Implementation
cppexamples/sorting/InsertionSort.cpp
        /**
 * Sort an array of integers using an insertion sort.
 *
 * Side Effects: The array is sorted  "in place".
 *
 * @param a        The array of integers
 * @param length   The number of elements in the array
 */
void sort(int a[], int length) {
  int i, j, temp;

  for (i = 1; i < length; i++) {
    temp = a[i];

    j = i;
    while ((j > 0) && (temp < a[j - 1])) {
      a[j] = a[j - 1];
      j--;
    }

    a[j] = temp;
  }
}
        
Efficiency Analysis
Efficiency Analysis (cont.)

\( T(n) = 1 + 2 + \cdots + (n-1) = n \cdot (n-1)/2 \)

So: \( T(n) = O(n^2) \)