# Recursive Sorts

## Recursive sorts

Let’s compare and contrast merge sort with quicksort.

Merge sort breaks down the original array into subarrays before building the final sorted array by merging sorted subarrays. If the size of the given `list` is even, the two subarrays will be of equal size. But if the size of the `list` is odd, then we’ll (arbitrarily) choose the left half as the smaller half.

``````def mergeSort(list):
size = len(list)
if (size <= 1):
return list
else:
mid = size / 2
smallerHalf = mergeSort(list[0:mid])
largerHalf = mergeSort(list[mid:size])
return merge(smallerHalf, largerHalf)
``````

### Question 1

Give the two subarrays that will be merged by the final step of merge sort on the following array.

``````[9, 1, 1, 3, 5, 5, 6, 8]
``````
Explanation

Merge sort is a recursive procedure, so it’s not necessary to simulate the entire sorting algorithm! We can just assume that `mergeSort` on the left/right halves will return the sorted version of that half.

Unlike insertion sort, selection sort, and heap sort, the recursive calls to `mergeSort` operate on each subarray rather than the entire array! Notice how an element from the right half will not swap to the left half until the final `merge` step.

### Question 2

In the worst case, quicksort has a worse asymptotic time complexity than merge sort. Explain why programmers might still prefer quicksort over merge sort.

### Question 3

Explain why programmers might prefer merge sort over quicksort.

## Partitioning

Partitioning around a pivot is an operation that reorganizes the elements in an array as follows.

``````[ (elements < pivot) pivot (elements >= pivot) ]
``````

### Question 1

Given the array `[4, 5, 1, 3, 7, 2, 6]`, which of the following arrays are valid partitions around the pivot 4?

Explanation

The pivot item goes to its correct sorted position at index 3. There must be 3 items less than 4 and 3 items greater than 4.

### Question 2

Given the following array, which value is chosen as the pivot if we define `choosePivot` as the median of the first, middle, and last elements.

``````[1, 9, 5, 4, 7, 2, 8, 6, 3]
``````

### Question 3

What is the state of the array after in-place partitioning around the pivot from the preceding question?

``````[1, 9, 5, 4, 7, 2, 8, 6, 3]
``````
Explanation
Input
``````[1, 9, 5, 4, 7, 2, 8, 6, 3]
``````
Swap pivot to front
``````[3, 9, 5, 4, 7, 2, 8, 6, 1]
``````
Start moving the fingers
``````[3, 9, 5, 4, 7, 2, 8, 6, 1]
^                    ^
Low                  High
``````
Swap and move both fingers inward
``````[3, 1, 5, 4, 7, 2, 8, 6, 9]
^              ^
Low            High
``````
Keep moving high down since both values are larger than pivot
``````[3, 1, 5, 4, 7, 2, 8, 6, 9]
^        ^
Low      High
``````
Swap and move both fingers inward
``````[3, 1, 2, 4, 7, 5, 8, 6, 9]
^  ^
Low  High
``````
Keep moving high down since both values are larger than pivot (stop when they cross)
``````[3, 1, 2, 4, 7, 5, 8, 6, 9]
^
Low  High
``````
Swap pivot to the end of the low section
``````[2, 1, 3, 4, 7, 5, 8, 6, 9]
``````