Overview

You’ve previously thought a bit about sorting a list, but it’s time to think a bit more about this seemingly simple problem by examining a classic recursive and fairly fast sorting algorithm: mergesort.

Basic Learning Objectives

Before class, you should be able to:

  • Explain the high-level idea of mergesort

Advanced Learning Objectives

After class, you should be able to:

  • Demonstrate the steps of mergesort on paper
  • Explain the idea of the time complexity of mergesort
  • Explain the implementation considerations of mergesort

Reading

You should read/watch the following and complete the embedded checks:

Checks

Submit an answer to the following on Moodle.

| 46 | 9 | 22 | 5 | 15 | 1 | 96 | 34

Draw out the steps in the mergesort algorithm to sort the list above. You should clearly show where the list is splitting into sublists. Drawing out the many sublists in mergesort may be tedious, so feel free to draw out your answers, take a picture or screenshot, and upload that.