12.1.5. Recursive Formulation

Try these first

1. 1.

   Explain the basic principle of insertion sort.

   Hint

   Think about how one would sort playing cards.

2. 2.

   What is the time complexity of insertion sort in the worst case?

   Hint

   Consider the number of comparisons needed in the worst-case scenario.

3. 3.

   What is the main idea behind insertion sort?

   • To compare all elements at once
   • To build a sorted array incrementally
   • To sort without comparisons

   Hint

   Think about how the algorithm progresses with each element.

4. 4.

   Is insertion sort efficient for small datasets?

   • True
   • False

   Hint

   Think about the ease of inserting few elements.

5. 5.

   Write a function that sorts an array using the recursive insertion sort approach and explain your thought process.

   Hint

   Think through how to keep your base case clear and how to recursively sort the smaller elements.

6. 6.

   Given a nearly sorted array, explain how insertion sort's efficiency changes and provide a justification.

   Hint

   Reflect on how comparisons are reduced in already sorted data.