Merge Sort Preparation

Overview

You’ve learned about several O(n²) 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/watch the following and complete the embedded checks:

• Runestone 5.11