Home | Tutorials | Articles | Videos | Products | Tools | Search
 Interviews | Open Source | Tag Cloud | Follow Us | Bookmark | Contact
 Data Structures > Sort > Insertion Sort

# Insertion Sort

The following example shows insertion sort implementation.

• Best case time complexity of insertion sort is O(n)
• Worst case time complexity of insertion sort is O(n2)
• Average case time complexity of insertion sort is O(n2)

 File Name  : com/bethecoder/tutorials/ds/sort/InsertionSort.java Author  : Sudhakar KV Email  : [email protected]

 ``` package com.bethecoder.tutorials.ds.sort; import java.util.Arrays; public class InsertionSort {   /**    * @param args    */   public static void main(String[] args) {     int[] list = { 6, 5, 1, 8, 3, 9, 4, 0, 2, 7 };     System.out.println("Before sort : " + Arrays.toString(list));     double timeTaken = insertionSortTimeTaken(list);     System.out.println("After sort : " + Arrays.toString(list));     System.out.println("Time taken for InsertionSort : " + timeTaken + " milliseconds.");   }   /**    * @param list    */   public static void insertionSort(int[] list) {     int i, temp, j;     for (i = 1; i < list.length; i++) {       temp = list[i];       for (j = i - 1; j >= 0; j--) {         if (list[j] > temp) {           list[j + 1] = list[j];         } else {           break;         }       }       list[j + 1] = temp;       System.out.println("Step " + i + " : " + Arrays.toString(list));     }   }   /**    * Sorts and returns the time taken in milliseconds.    *     * @param list    * @return    */   public static double insertionSortTimeTaken(int[] list) {     long startTime = System.nanoTime();     insertionSort(list);     long timeTaken = System.nanoTime() - startTime;     return timeTaken * Math.pow(10, -6);   } }```

It gives the following output,
```Before sort : [6, 5, 1, 8, 3, 9, 4, 0, 2, 7]
Step 1 : [5, 6, 1, 8, 3, 9, 4, 0, 2, 7]
Step 2 : [1, 5, 6, 8, 3, 9, 4, 0, 2, 7]
Step 3 : [1, 5, 6, 8, 3, 9, 4, 0, 2, 7]
Step 4 : [1, 3, 5, 6, 8, 9, 4, 0, 2, 7]
Step 5 : [1, 3, 5, 6, 8, 9, 4, 0, 2, 7]
Step 6 : [1, 3, 4, 5, 6, 8, 9, 0, 2, 7]
Step 7 : [0, 1, 3, 4, 5, 6, 8, 9, 2, 7]
Step 8 : [0, 1, 2, 3, 4, 5, 6, 8, 9, 7]
Step 9 : [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
After sort : [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Time taken for InsertionSort : 0.491403 milliseconds.
```