1.
Show, in the style of the trace of Algorithm 2.4 (
p. 180
), the result of using mergesort
to sort the keys:
N O T H A R D T O M E R G E S O R T
2. [Exercise 2.2.16 in Algs4 preliminary edition]
Develop a linearithmic algorithm for computing the number of inversions in a given array (the number of exchanges that would be performed by insertion sort for that array). Give a crisp and concise English description of your algorithm—don't
write Java code.