Insertion Sort

Problem

Insertion Sort is a simple sorting algorithm that builds the final sorted array one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort, but it has advantages for small data sets and is often used as part of more sophisticated algorithms.

Examples:

Example 1:
Input: arr = [12, 11, 13, 5, 6]
Output: [5, 6, 11, 12, 13]
Explanation: The algorithm builds the sorted array one element at a time by inserting each element at its correct position.

Example 2:
Input: arr = [5, 2, 4, 6, 1, 3]
Output: [1, 2, 3, 4, 5, 6]
Explanation: Each element is compared with the elements to its left and inserted at the correct position.

Solution

Intuition

  • Insertion Sort works the way we sort playing cards in our hands.
  • The array is virtually split into a sorted and an unsorted part.
  • Values from the unsorted part are picked and placed in the correct position in the sorted part.
  • It's efficient for small data sets and nearly sorted arrays.

Approach

  • Start from the second element (index 1) and consider it as part of the unsorted array.
  • Compare this element with the elements in the sorted array (elements to its left).
  • Shift all elements in the sorted array that are greater than the current element to the right.
  • Insert the current element at the correct position in the sorted array.
  • Repeat for all elements in the unsorted array.

Complexity Analysis

  • Time Complexity: Best case: O(n) when the array is already sorted. Average and worst case: O(n²).
  • Space Complexity: O(1) as it sorts in-place, requiring only a single additional memory space for the temporary variable.
Implementation
CPP
Run your code to see output here