Sorting algorithms 3 - Insertion sort

Just like bubble and selection sorts, insertion sort is also a simple yet inefficient sorting algorithm on large data sets.

Process

• Lets take a hypothetical moment where the unsorted array we want to sort is partially sorted.
• So the left part is sorted in ascending order and right part is not yet sorted.
• we will mark first element in the unsorted part as out. That indirectly says that the last element in sorted portion we can mark as in-1, if we say in = out
• So now,we can take in-1 th element and move sorted portion until we find a place to put in-1.
• When that happens, unsorted portion decreases by 1. That means out decrements by 1 and sorted portion increases by  1 position.
• The data structure is sorted when out goes from 1 to length of the data structure.

// Insertion sort implementation
 public int[] insertionSort(int[] array) {

  for (int out = 1; out < array.length; out++) {
   int in = out;
   int temp = array[out];
   
   while (in>0 && temp<= array[in-1]){
    //move sorted portion to have some space to array[in-1]
    array[in] = array[in-1];
    in --;
   }
   
   array[in] = temp;
  }

  return array;
 }