Link Search Menu Expand Document
CSE 373

Recursive Sorts

Table of contents

  1. Merge sort
  2. Quicksort
  3. In-place partitioning demo
  4. Recursive sorts
  5. Partitioning

Merge sort

Quicksort

In-place partitioning demo

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]