Overview

You’ve learned about several O(n2) sorting algorithms. However, there are several faster ways to sort a list of items using recursion. Today’s focus will be on one called merge sort.

Basic Learning Objectives

Before class, you should be able to:

  • Explain the idea of divide and conquer strategies
  • Explain the high-level idea and steps of merge sort

Advanced Learning Objectives

After class, you should be able to:

  • Explain a recursive implementation of merge sort
  • Implement merge sort on paper

Resources

You should read the following and complete the embedded checks:

Checks

Draw out the merging after the following split of the list ["ant", "dragon", "zero", "cold", "azure", "boy", "fix"]. Your diagram should look similar to Figure 11 from the reading. Upload a picture of your merging diagram to Moodle.

A diagram of a merge sort split

Remember that your final list should be sorted from “ant” to “zero”.