1. Quicksort (Simplified Split)

You are given the following simplified version of split to be used in quicksort:

int split(int[ ] A, int lo, int hi) {

int sp = lo; int pivot = A[lo];

for (int i=lo+1; i <= hi; i++) {

if (A[i] < pivot) {

sp++;

// swap

int temp = A[i]; A[i] = A[sp]; A[sp] = temp;

}

}

// swap

A[lo] = A[sp]; A[sp] = pivot;

return sp;

}

Given the following array of integers:

28 10 8 30 32 37 41 22 45

a) Execute quicksort on this array using the above split method. Show the resulting sort tree, in which each

node is the (sub)array to be sorted at that level - the root is the full array. Next to each node write the number

of array-item-to-pivot comparisons and data swaps (// swap in code) required to split it.

b) In part (a), if insertion sort (and not recursive quicksort) were to be applied on the two sub arrays imme- diately after the first split, what would be the total number of comparisons to sort? Show work.