04. Insertion Sort

Algorithm Pseudocode

  1. Partition the array into two subarrays - the first value will be the "sorted" array, and the others will be in an "unsorted" array.
  2. Take the first value x in the unsorted array and store into a temp.
  3. Moving down the list in the sorted array, shift over every element greater than x.
  4. Insert x and repeat.


Here's a nifty animation for your better learning.


Insertion sort is the best choice when data is nearly sorted or the problem size is small. Thus, it's a good choice for higher divide-and-conquer sorting algorithms such as merge sort and quick sort.

Furthermore, it is considered to have low overhead since it avoids executing unneccesary lines of code.

Insert sort is stable sorting algorithm.


If our array is already sorted, only n-1 comparisons are used. In the worst case, n(n-1)/2 comparisons are used. Time: O(n2) Space: O(1)

Implementation in Java

Here's a sample implementation written in Java. Note that it extends the Sort.java class.

import java.util.Arrays;
public class InsertionSort extends Sort {
  public static void main(String[] args) {
    int[] testInt = {1,6,2,3,6,7,4,2,5};
  public static void insertionSort(int[] test) {
     * The array will be partitioned to two subarrays - the sorted
     * and unsorted. The first element will be in our sorted subarray.
    for (int i = 1; i < test.length; i++) {
      // Store the element to insert
      int temp = test[i];
       * For every element in our sorted subarray that is greater 
       * than the temp, shift elements over one. 
      for (int j = i-1; j >= 0; j--) {
        if (temp < test[j]) {
          test[j+1] = test[j];
        } else {
          test[j+1] = temp;

Learn how data is stored

Data Structures and Algorithms in Java

Learn how data is stored Try Data Structures

Algorithms are the procedures that software programs use to manipulate data structures. Besides clear and simple example programs, the author includes a workshop as a small demonstration program executable on a Web browser. The programs demonstrate in graphical form what data structures look like and how they operate.

$ Check price
64.9964.99Amazon 4.5 logo(97+ reviews)

More Data Structures resources

Aching back from coding all day?

Foam Seat Cushion

Aching back from coding all day? Try Back Problems

This foam seat cushion relieves lowerback pain, numbness and pressure sores by promoting healthy weight distribution, posture and spine alignment. Furthermore, it reduces pressure on the tailbone and hip bones while sitting. Perfect for sitting on the computer desk for long periods of time.

$ Check price
99.9599.95Amazon 4.5 logo(9,445+ reviews)

More Back Problems resources