12.1.2. Insertion Process

Try these first

1. 1.

   What does insertion sort do?

   Hint

   Think about how cards are sorted.

2. 2.

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

   Hint

   Consider the scenario of sorting a completely reversed list.

3. 3.

   What is the main process of insertion sort?

   • A. Sorting by selection
   • B. Inserting elements into-their position
   • C. Merging sorted lists
   • D. Swapping elements randomly

   Hint

   Remember how we sort cards.

4. 4.

   True or False: Insertion sort is more effective on large, unsorted datasets than on nearly sorted data.

   • True
   • False

   Hint

   Think about the efficiencies we discussed.

5. 5.

   Given an array of integers [5, 2, 9, 1, 5, 6], illustrate each step of the insertion sort process.

   Hint

   Visualize the process as inserting numbers one by one into an already sorted list.

6. 6.

   Analyze the effectiveness of using insertion sort on a dataset of 1,000 elements that is nearly sorted. What is the expected time complexity?

   Hint

   Think about the efficiency of comparisons in nearly sorted arrays.