Merge Sort

The other sorting algorithms we’ve covered in the class – selection sort, insertion sort, and bubble sort – all suffer from the same general limitations and thus suffer the same, generally slow, worst-case runtime of O(n²). Merge sort, though, behaves in a fundamentally different manner, leveraging recursion to “pass the buck” of sorting but also accomplishing something drastically superior – O(n log n) runtime.

• Lecture

  • Watch on Youtube
  • Watch on the CS50 Video Player
  • Download Lecture
  • Lecture Notes

• Shorts

  • Merge Sort
  • Merge Sort (Rob)

• Notes

  • Merge Sort

• Supplementary Resources

  • Khan Academy on Merge Sort.

• Thought Questions

  • What are the most significant tradeoffs associated with merge sort that we don’t have to deal with in any of the n² sorts we’ve seen thus far?
  • In what situations is merge sort the best option for sorting?
  • How would you compare and contrast the sorting algorithms we’ve already looked at? Take care to consider their respective time and space complexities.