NAMES:
LOGINS:
PRECEPT:
COS 226 Exercises on Sorting 2
References: Lectures 5-6 and Sections 3.2-3.3 in Algs4
1.
Show, in the style of the trace on page 237, the result of using mergesort
to sort the keys
E A S Y T O M E R G E S O R T
2.
Suppose that the result of the shuffle in Algorithm 3.5
is P A R T I O N E D H F L.
Show the result of the first call on partition().
Give the contents of the array after each exchange.
3.
Suppose that the result of the shuffle in Algorithm 3.5
is 1 0 0 1 1 1 0 0 0 0 0 1 0 1 0 0.
Show the result of the first call on partition().
Give the contents of the array after each exchange.
Warning: pay special attention to how the algorithm works
when a key is equal to the partitioning element.