Overview

Mergesort is pretty good, but with some small tweaks, it can get even better. It’s time to think a bit more about this seemingly simple problem by examining one of the fastest sorting algorithms: quicksort.

Basic Learning Objectives

Before class, you should be able to:

  • Explain the high-level idea of quicksort
  • Define the terms pivot value and split point
  • Explain why quicksort is typically faster than other sorting algorithms

Advanced Learning Objectives

After class, you should be able to:

  • Implement your own median of three algorithm
  • Analyze how different factors of a list impact quicksort’s performance
  • Explain the idea behind the Big-O of quicksort

Reading

You should read the following:

Checks

Submit answers to the following (I recommend drawing out the sorting on paper and uploading a picture):

  1. Given the list [4, 5, 6, 1, 2, 3]
    • Draw out the steps of mergesorting the list
    • Draw out the steps of quicksorting the list
  2. What are the main differences in the implementation of quicksort and mergesort?