Insertion Sort Algorithm Worksheet

Insertion Sort Algorithm

Read each question carefully and provide your answers in the space provided. Show all your work for full credit.

Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, insertion sort provides several advantages:

1. Simple implementation. 2. Efficient for (and works fast on) small data sets. 3. Efficient for data sets that are already substantially sorted. 4. Stable; i.e., does not change the relative order of elements with equal keys. 5. In-place; i.e., only requires a constant amount O(1) of additional memory space.

1. Briefly explain the main idea behind the Insertion Sort algorithm.

2. List two advantages of using Insertion Sort.

1. Insertion sort builds the final sorted array one   at a time.

2. For large datasets, Insertion Sort is generally less efficient than algorithms like   sort or   sort.

Apply the Insertion Sort algorithm to sort the following array in ascending order. Show each step of the process clearly.

[8, 2, 4, 9, 3, 6]

1. What is the time complexity of Insertion Sort in the worst-case scenario?

2. When is Insertion Sort most efficient?

1. Insertion Sort is an unstable sorting algorithm.

2. Insertion Sort requires O(1) additional memory space.

1. Describe a scenario where Insertion Sort would be a preferred sorting algorithm over more complex ones like Quick Sort.