Class12.md

Class 12: Friday, April 14 – Divide-and-Conquer Recursion

Topics:

• divide-and-conquer recursion: divide, conquer, combine
• revisit binary search to see how it divides and conquers
• merge algorithm and merge sort

Resources:

• read Brian Hans's merge sort article with animations and pseudocode
• play with USF's interactive sorting animations to follow algorithms step-by-step
• watch Toptal's sorting animations to see how algorithms compare based on input data and read the discussion section
• watch videos to observe patterns: 9 sorting algorithms, 15 sorting algorithms, 23 sorting algorithms

Challenges:

• implement merge algorithm that combines two sorted lists into one sorted list
  • merge(list1, list2) - return a list containing all elements in order from list1 and list2, which are assumed to be in order
• implement non-recursive merge sort that uses any other sorting algorithm to sort sublists
  • merge_sort(items) - return a list containing all elements of items in sorted order
  • use the divide-and-conquer problem-solving strategy:
    1. Divide: split problem (input list) into subproblems (two sublists of half size)
    2. Conquer: solve subproblems independently (sort sublists with any sorting algorithm)
    3. Combine: combine subproblem solutions together (merge sorted sublists)
• implement recursive merge sort that calls itself to sort sublists recursively
  • remember to add a base case to avoid infinite recursion loops (hint: very small lists are always sorted)
• annotate your merge and non-recursive merge_sort functions with complexity analysis
• write unit tests for your sorting algorithms
  • include test cases of varying sizes and edge cases

Stretch Challenges:

• implement bucket sort for integers using a divide-and-conquer recursive style

Project:

• sorting algorithms with real-world data on Make School's Online Academy