Quicksort and Mergesort Exercises

Consider the following array of integers a: 

  0  1  2  3  4  5  6  7  8  9  (index)
 ______________________________
|                              |
| 6  2  7  1  9  8  5  3  4  0 |(value)
|______________________________|
  1. Quicksort

    1. Show the array after the first call to partition.

    2. The original call to the qsort method would be qsort(a,0,9). Show the recursive calls that are made directly from this initial call to qsort, and the calls that are made directly from each of those calls. You can refer to the array simply as a.

  2. Mergesort

    1. Show a stack with the first 8 calls to Mergesort. As above, you can refer to the array simply as a. Cross off completed calls as we did in class.

    2. If the merging operation were done by a separate method merge(a, lo, hi) (as in the pseudocode we gave in class -- assume that merge will calculate the midpoint itself), show what calls to merge would appear in the above stack.