December 1st, 2014

The Merge Sort
Visit ClassroomSalon.com

Homework:
0. Is mergesort faster than shellsort? Explain your rationale.

1. Does the abstract in-place merge produce proper output if and only if the two
input subarrays are in sorted order? Prove your answer, or provide a counterexample.

2. Give a trace, in the style of the trace given at the beginning of this section, showing how the keys A E Q S U Y E I N O S T are merged with the abstract in-place merge() method.

3. Geometric increments. Run experiments to determine a value of t that leads to the lowest running time of shellsort for random arrays for the increment sequence 1,[t],[t^2],[t^3],[t^4],[t^5], . . . for N = 10^6. Give the values of t and the increment sequences for the best three values that you find.