Insertion Sort

What You’ll Learn 📚

• Understand what Insertion Sort is and how it works
• Learn key terminology related to sorting algorithms
• Work through progressively complex examples
• Get answers to common questions and troubleshoot issues

Introduction to Insertion Sort

Insertion Sort is a simple and intuitive sorting algorithm. Imagine sorting a hand of playing cards: you pick up each card one by one and insert it into its correct position among the cards you’ve already sorted. That’s exactly how Insertion Sort works! It’s great for small datasets and is easy to implement.

Key Terminology

• Algorithm: A step-by-step procedure for solving a problem.
• Sorting: Arranging data in a particular order (e.g., ascending or descending).
• In-place: An algorithm that requires a small, constant amount of extra space.

Let’s Start with a Simple Example 🌟

def insertion_sort(arr):
    # Traverse through 1 to len(arr)
    for i in range(1, len(arr)):
        key = arr[i]
        # Move elements of arr[0..i-1], that are greater than key,
        # to one position ahead of their current position
        j = i-1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

# Example usage:
arr = [12, 11, 13, 5, 6]
insertion_sort(arr)
print("Sorted array is:", arr)

Progressively Complex Examples

Example 1: Sorting a Small Array

arr = [3, 1, 4, 1, 5]
insertion_sort(arr)
print("Sorted array is:", arr)

Example 2: Sorting with Duplicates

arr = [2, 3, 2, 1, 4, 1]
insertion_sort(arr)
print("Sorted array is:", arr)

Example 3: Sorting a Larger Array

arr = [10, 7, 8, 9, 1, 5, 3, 6, 2, 4]
insertion_sort(arr)
print("Sorted array is:", arr)

Common Questions and Answers

1. Q: Why is it called Insertion Sort?

   A: Because each element is inserted into its correct position in the sorted portion of the array.

2. Q: Is Insertion Sort stable?

   A: Yes, it maintains the relative order of equal elements.

3. Q: What is the time complexity of Insertion Sort?

   A: The average and worst-case time complexity is O(n^2), but it performs well on small or nearly sorted datasets.

4. Q: Can Insertion Sort be used on linked lists?

   A: Yes, it can be adapted for linked lists, where it performs well with O(1) space complexity.

5. Q: How does Insertion Sort compare to other sorting algorithms?

   A: It's simpler and more efficient for small datasets compared to more complex algorithms like Quick Sort or Merge Sort.

Troubleshooting Common Issues

Ensure that your loop indices are correctly managed to avoid index errors.

Remember, practice makes perfect! Try sorting different types of arrays to get comfortable with the algorithm.

Practice Exercises

• Sort the array [9, 7, 5, 3, 1] using Insertion Sort.
• Modify the algorithm to sort in descending order.
• Implement Insertion Sort in a different programming language.

For more information, check out the Wikipedia page on Insertion Sort.