Web Development Articles

An insertion sort processes a single value in each step. It works on the principle of inserting a single element into an existing ordered list. At each step, the inserted value is put into the list so that that overall list maintains its order. This is viewed as more efficient than adding the element anywhere in the list, then re-sorting the whole list.

The first step of the algorithm involves inserting the second element in the unordered list into the new single-element list which simply contains the first element of the original unordered list. The third element of the original list is then inserted into the correct position in the ordered list (of two elements). The single-element list used to initiate the algorithm is viewed as an ordered list.

The Insertion Sort is a simple algorithm to implement and is efficient on relatively small lists or sets of data but it is inefficient for large sets of data. This is explained by the time complexity of the Insertion Sort which is O(N²). This means that as the data input increases, the time taken to execute the algorithm will increase at an ever increasing rate. The Insertion Sort uses less memory than the two following sort algorithms.

A Java implementation of the Insertion Sort is shown below. To use this class, another class can create an InsertionSort object then call the sort() method within it. An unordered list of integers is to be sorted using this Java implementation but it can be applied to other data types as well.

/**
 * The class InsertionSort
 *
 * @author  Jon Jackson
 */
public class InsertionSort
{
  // instance variables
  private int i, n, newElement, location;
  private int[] list;

  /**
   * The main sort method.
   * @param list - the list to be sorted
   */
  public void sort(int[] list)
  {
    n = list.length;
    // for all elements in the list (excluding the first one)
    for (i = 1; i < n; i++)
    {
      // store element to be inserted in a variable
      newElement = list[i];
      location = i-1;
      // find location in list where new element should be inserted
      while (location >= 0 && list[location] > newElement)
      {
        // shift element up one place in list
        list[location + 1] = list[location];
        // look at next element down in list
        location = location - 1;
      }
      // insert new element into list
      list[location + 1] = newElement;
    }
  }
}

Check out the Computation and Algorithms section of the Computing Students website for information on some other search and sort algorithms.

Another useful resource: Algorithms & Data Structures.