Insertion Sort

About

Insertion Sort builds a sorted array one element at a time. It splits the array into a "sorted" part on the left and an "unsorted" part on the right. It takes the next element from the unsorted side, shifts larger elements in the sorted side out of the way, and inserts it into its correct position—exactly like sorting a hand of playing cards as you are dealt one card at a time.

![[ins.mp4]]

Complexities

• Time Complexity:
  • Best: $O(n)$
  • Worst/Average: $O(n^2)$
• Space Complexity: $O(1)$

Code Implementation

def insertion_sort(arr):
    # Loop from the second element (index 1) to the end
    for i in range(1, len(arr)):
        key = arr[i] # The element we want to insert into the sorted part
        j = i - 1
	    
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]  # Shift element to the right
            j -= 1
            
        # Place the key at its correct sorted position
        arr[j + 1] = key
        
    return arr

Key Takeaways

• Shifting vs. Swapping: Unlike Bubble Sort, which executes a multi-line variable swap over and over, Insertion Sort simply overrides positions by shifting elements to the right. This requires fewer operations.
  
  
• Online Algorithm Advantage: Insertion sort is an "online" algorithm—it can sort a list as it receives it. If you are continuously feeding new data stream elements into an already sorted list, it inserts them efficiently at $O(n)$ time.
  
  
• When to Use It:
  
  
  • Fantastic for nearly sorted data or small arrays (typically fewer than 10–20 elements).
    
    
  • In fact, complex commercial algorithms like Timsort (used in Python's sort()) and IntroSort (used in C++ std::sort) switch internally to Insertion Sort when working on small subsets of data because its low overhead makes it faster than Quick Sort or Merge Sort at that scale.