12.1. Insertion Sort

Try these first

1. 1.

   What is the first step in Insertion Sort?

   Hint

   Think about which element you start with.

2. 2.

   How do you find where to insert an element?

   Hint

   Use backward comparison.

3. 3.

   What is the best-case time complexity of Insertion Sort?

   • O(n)
   • O(n^2)
   • O(log n)

   Hint

   Think about how many comparisons are made in a sorted array.

4. 4.

   True or False: Insertion Sort can be implemented iteratively?

   • True
   • False

   Hint

   Recall how you can loop through elements.

5. 5.

   Analyze the performance of Insertion Sort for various inputs: completely unsorted, completely sorted, and reverse sorted arrays. Discuss how each scenario affects the time complexity.

   Hint

   Consider the comparisons and shifts needed for each case.

6. 6.

   Write a performance comparison between Insertion Sort and Quick Sort on the basis of average runtime across 10,000 random numbers.

   Hint

   Think about how swaps and partitioning differ in handling elements in these sorts.