Practice Merge Sort

Enhance your understanding of the Merge Sort algorithm with these exercises:

Exercise 1: Manual Trace

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

[ 14, 7, 3, 12, 9, 11, 6, 2 ]

For each recursive call:

1. Draw the array divisions at each step
2. Show the state of all subarrays during the merge operations
3. Illustrate how the final sorted array is built from bottom up

Exercise 2: In-place Merge Sort

The standard implementation of Merge Sort requires O(n) extra space. Try to implement an in-place version that minimizes additional space usage.

Hint: Look into using the "rotate" operation to shift elements efficiently when merging.

Exercise 3: Bottom-Up Merge Sort

Implement a non-recursive (iterative) version of Merge Sort that works bottom-up. Start by merging subarrays of size 1, then size 2, 4, 8, and so on.

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

Trace your algorithm's execution through the array above.

Exercise 4: Counting Inversions

An inversion in an array is a pair of elements that are out of order (i.e., a[i] > a[j] where i < j). Modify the Merge Sort algorithm to count the number of inversions in an array.

For example, the array [3, 1, 4, 2] has 2 inversions: (3,1) and (4,2).

Calculate the number of inversions in this array:

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

Exercise 5: Merge Sort for Linked Lists

Adapt the Merge Sort algorithm to work efficiently on linked lists instead of arrays. How does this affect the performance characteristics of the algorithm?

What are the advantages of using Merge Sort specifically for linked lists compared to other sorting algorithms?

Interactive practice exercises with step-by-step feedback coming soon!