Skip to main content

Divide-and-Conquer Sorts

Overview​

This lesson covers two sorting algorithms that use the "divide-and-conquer" method: merge sort and quick sort.

There are three components to this lesson:

  1. myGA module: Divide-and-Conquer Sorting Algorithms
    • If the above link does not take you to the correct module, you can find the lesson in your myGA dashboard.
  2. In-Class Exercise: Implementing Merge Sort
  3. In-Class Exercise: Implementing Quick Sort

Note: The myGA module contains a link to an exercise in CodePen. The code in CodePen is the exact same as the code for the in-class exercises. Try out the exercise in CodePen and see how far you can get with it. Leave off where you get stuck and we'll review the solution in class.

Learning Objectives​

By the end of this lesson, you 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.

Prerequisites​

  • Big O Notation
  • Recursion
  • Intro to Sorting

Duration​

2.5 hours total:

  • 0.5 hour myGA
  • 2 hours in class

Additional Resources​