Lesson 20: Mergesort and Quicksort

Outline:

  1. Questions?
  2. Merge sort
    • algorithm overview
    • runtime
  3. Quicksort
    • algorithm overview
    • example implementation: Quicksort.kt
    • runtime
  4. Wrap-up

What’s next

  • Quiz 7 will be next Monday and cover the following Quiz Learning Objectives:
    • TR 1: tree traversal (new!)
    • TR 2: binary search tree insertion/deletion (new!)
    • TR 4: debugging trees (new!)
    • OO 3: inheritance
    • QQ 2: queue time complexity
  • Assignment 6 is due next Wednesday

What you should do now:

  • The readings (see below)
  • Work on Assignment 6 this weekend

Reading assignment (to be completed by the next class):

Sorting (from today):

Heaps (for next time):