What is Insertion Sort?

Insertion Sort is a simple comparison-based sorting algorithm that sorts an array by iteratively building a sorted sublist from the unsorted portion of the input array. It is best suited for small arrays or arrays that are already partially sorted.

Time and Space Complexity

Time Complexity:

• Best-case scenario: O(n) - This occurs when the input array is already sorted. In this case, the algorithm only needs to make one pass through the array to confirm that it is sorted.
• Average-case scenario: $O(n^2)$ - This occurs when the input array is in random order. The algorithm has to compare and potentially move elements multiple times, leading to a quadratic time complexity.
• Worst-case scenario: $O(n^2)$ - This occurs when the input array is in reverse order. The algorithm has to move elements the maximum number of times, leading to a quadratic time complexity.

Space Complexity:

• O(1) - The algorithm is an in-place sorting algorithm, meaning it doesn't require additional storage space to be allocated. It only uses a constant amount of extra memory (for temporary variables) while sorting the input array.

How does it work?

Insertion Sort divides the given array into two parts - sorted and unsorted

For the unsorted part, take the first element and place it at the correct position in the sorted array. Shove all the elements which are larger than 1st element by one position.

Example

1. pick the first element (which is 3) and that is considered the “sorted” side

2. The actual algo starts in the second element

   

3. You first create a temp variable which holds the value of the current unsorted element you are trying to sort. This will create an “empty” space in the array