Insertion Sort

We'll explore Insertion Sort, a straightforward and intuitive algorithm ideal for understanding the core principles of sorting.

How Does Insertion Sort Work?

Imagine you have a messy desk full of papers. Insertion Sort is like meticulously going through each paper, comparing it to its neighbors, and inserting it into its rightful place to achieve a neat stack. Here's a step-by-step breakdown:

Start at the second element (consider the first element already sorted). Compare the current element with the previous element. If the current element is smaller, shift the larger element one position to the right to create a space. Insert the current element into the empty space. Repeat steps 2-4 for all remaining elements. This process mimics sorting playing cards in hand, making Insertion Sort an easy-to-grasp algorithm.

def insertion_sort(data):
 
  for i in range(1, len(data)):
    key = data[i]  # Current element to be inserted
    j = i - 1  # Index of the previous element
 
    # Shift elements to the right until a suitable position is found for the key
    while j >= 0 and data[j] > key:
      data[j + 1] = data[j]
      j -= 1
    data[j + 1] = key  # Insert the key at the correct position
 
  return data
 
# Example usage
unsorted_data = [8, 3, 1, 4, 2]
sorted_data = insertion_sort(unsorted_data.copy())  # Avoid modifying original list
print(f"Unsorted data: {unsorted_data}")
print(f"Sorted data: {sorted_data}")
 

Strengths

Easy to understand and implement, efficient for small datasets.

Weaknesses

Performance degrades significantly for large datasets (quadratic time complexity). While Insertion Sort might not be the most powerful tool for massive datasets, it excels as a learning tool for grasping sorting algorithms and their core operations.