Question

[6 marks] Suppose we run three sorting methods on copies of an array containing 1, 7, 19, 24, 7, 49 (in that order). Suppose we stop each method before it is complete (as described below). In each case, give the order of the values as they would appear in the array after we stopped each sort. a. Quick sort (that uses the median-of-three technique to find its pivot) stopped IMMEDIATELY BEFORE the first recursive call starts. b. Radix sort stopped IMMEDIATELY AFTER the first iteration of the outermost loop. c. Recursive merge sort stopped IMMEDIATELY AFTER the first recursive call is finished.

Answer 1

1.In this median of three algorithm we first find the median of first and last

So in the array

1711912417149

the median of 1 and 49 will be 19 so the pivot element will be 19 no what will happen before the first loop is smaller then 19 will be on its left side ans larger or equal then 19 will be on right side

So the array before the 1st recursion will be:

171711912449

Which is sorted indeed

2. Radix sort sorts from least significant digit to the most significant digit

So at the end of first outer loop it will sort only according to the weightage of least significant digit so the array will be

[1247|19149

3.In merge sort first recursive call will only finish after all will finish because it will keep calling itself until the last returns so the array will be final array

171711912449