Insertion Sort Algorithm / Pseudocode

Well for anyone interested in Computer Science, one of the first lessons would be regarding Sorting. Why sorting is important?…. This is very important as the first step of Software Engineering/Development is understanding the problem(business need).

Why Sorting? Many problems become easy if our arrays/lists are sorted (For example finding the median, finding a specific number, finding min/max, generating a hashcode based on words, …..)

So simply put, sorting is important. Follow the links in resources for additional reasoning on why sorting is important before you review the algorithm.

The main idea behind this algorithm is to insert a new element into an already sorted array by performing pairwise swapping.

1. Consider each element i from 1 to n 
2. Consider j from i to 0
3. Compare j with j-1 in each step(pairwise comparision) and swap if needed.

The pseudocode version 1 is as follows

for i: 1 to n{
   for j: i to 0{
      if(a[j] < a[j-1]){
          swap a[j] and a[j-1]
      }
   }
}

Note that you end up swapping the inner loop in this version till 0 every time even if the element is already at its original place or somewhere in between. So one suggestion might be to break when the condition fails to save some time.

for i: 1 to n {
   for j: i to 0 {
      if(a[j] < a[j-1]){
          swap a[j] and a[j-1]
      }else{
          break
      }
   {
}

Another way or an elegant way of writing this is as

for i: 1 to n {
   newElement = a[i]
   j = i-1
   while(j > 0 && a[j-1] < newElement){
     swap a[j], a[j-1]
     j--
   }
}

Time complexity: O(n²) (n steps for the first loop to consider each element and n again looping to move the element to its right place = n x n)
Space complexity: O(1) (no additional space needed)

Further Improvements to be considered:
Consider while inserting the element to its right place we are taking up n time. If we use binary search it would take us to log n time instead for the step. However, as we need to shift our elements, it would take up n time in the worst case. This can be a useful enhancement when we have a different data structure such as a Linked list.

Resources:
MIT Algorithms Lecture (https://www.youtube.com/watch?v=Kg4bqzAqRBM)

Feel free to correct or suggest or comment about anything in the explanation.