Practice Insertion Sort

Try working through these insertion sort exercises to test your understanding:

Exercise 1: Manual Trace

Trace through the Insertion Sort algorithm step by step with the following array:

[ 7, 3, 9, 2, 1, 5 ]

For each iteration, track:

1. Which element is the "key" element being considered
2. How the sorted portion changes as you insert the key
3. The state of the array after each insertion

Exercise 2: Optimization

Can you optimize the basic Insertion Sort to improve its performance for:

1. Arrays that are already almost sorted?
2. Arrays with many duplicate elements?

Hint: Consider binary search as a way to find the insertion point faster.

Exercise 3: Challenge

This array is in reverse order. How many comparisons and shifts will Insertion Sort need to perform to sort it?

[ 9, 8, 7, 6, 5, 4, 3, 2, 1 ]

Can you derive a formula for the number of operations in the worst case?

Exercise 4: Implementation

Try implementing a variation of Insertion Sort that works from right to left rather than left to right. The first element to be inserted would be the second-to-last element, and the array would grow sorted from right to left.

Interactive practice exercises coming soon!