Overview
This lesson covers two sorting algorithms that use the “divide-and-conquer” method: merge sort and quick sort.
Prerequisites
- Big O Notation
- Recursion
- Intro to Sorting
Learning Objectives
By the end of this module, learners will be able to:
- Describe how to use merge sort and quick sort to sort data.
- Explain the space and time complexities of merge sort and quick sort.
- Identify when to use merge sort or quick sort in a given scenario.
Content
There are two components to this module:
- Lesson: Divide-and-Conquer Sorting Algorithms
- Exercise: Implementing Merge Sort & Quick Sort
Solution Code
- Exercise Solution: Merge Sort
- Exercise Solution: Quick Sort
Time to Complete
2.5 hours total:
- 0.5 hour - Divide-and-Conquer Sorting Algorithms Lesson
- 2 hours - Implementing Merge Sort and Implementing Quick Sort Exercises
Additional Resources
- Check out this visualization for both merge sort and quick sort: An interactive tool for visualizing sorting algorithms.
- Revisit our folk-dancing friends, now showing merge sort and quick sort: Fun videos demonstrating sorting algorithms through dance.
- This tool is useful for understanding how quick sort works: An interactive tool for visualizing quick sort.
- Watch how these algorithms look sketched out for merge sort and quick sort: Video tutorials on merge sort and quick sort.
Internal resources
Find a 👾 bug 👾 or have suggestions? Let us know!