Insertion Sort

Insertion sort is one of the most fundamental comparison based stable sorting algorithm. It is also known as playing card sort. It is based on a fundamental principle that a single element array is already sorted.  A two element array requires single comparison to sort it. A three element array can be visualized as two sub arrays (first with 2 elements and second with one element). So in each iteration, a new value is added to an already sorted sublist. 

a1 = {101}   // already sorted
a2 = {101, 2} // can visualize it as, add 2 to a already sorted sub-array having 101
       {2, 101} // one comparison required to put 2 in proper place
a3 = {101, 2, 5} // a new number added to a2
        {2, 101, 5}
        {2, 5, 101}  // put 5 in proper place

To visualize how it works, check out animation on wikipedia.

Java Implementation

/**
 * Insertion sort implementation
 * 
 * @author Siddheshwar
 *
 */
public class InsertionSort {
 /**
  * Insertion sort in ascending order
  * 
  * @param arr
  * @return arr
  */
 public int[] sort(int[] arr) {
  int tmp = 0;
  for (int i = 1; i < arr.length; i++) {
   for (int j = i; j > 0 && arr[j] < arr[j - 1]; j--) {
    tmp = arr[j];
    arr[j] = arr[j - 1];
    arr[j - 1] = tmp;
   }
   print(arr);
  }
  return arr;
 }

 // print current state of array
 private void print(int[] arr) {
  System.out.println();
  for (int i = 0; i < arr.length; i++) {
   System.out.print(arr[i] + "  ");
  }
 }

 public static void main(String[] args) {
  int[] arr = { 12, 11, 13, 5, 6 };
  InsertionSort is = new InsertionSort();
  arr = is.sort(arr);
  // is.print(arr);
 }
}

Output:

11  12  13  5  6  

11  12  13  5  6  

5  11  12  13  6  

5  6  11  12  13 

Performs ideal when array is nearly sorted or size is small. It can also be used as base sorting algorithm in recursive divide and conquer quick sort and merge sort algorithms.

Important Points

• If the array is already sorted, swapping will never be performed and hence time complexity will be O(n). Adaptive sorting algorithm. 
• Average and worst case time complexity is O(n^2). Space complexity is O(1)
• Worst performance when array is reverse sorted. 
• Not ideal approach if data is random.
• In the best case (when already sorted), all the elements are in proper place so it takes linear time. 
• In-efficient for value based data with large memory footprint as amount of memory shift/swap will be high. Performs good when sorting on pointer based data. 

References:
https://www.khanacademy.org/computing/computer-science/algorithms/insertion-sort/a/insertion-sort

---

keep coding !