Reading: Divide and Conquer 1

Reading¶

• Wikipedia:
  • Divide & Conquer
  • Merge Sort — Most relevant: from the beginning through the first “Top-down implementation,” the “Analysis” section, and “Comparison with other sort algorithms.”
  • Quicksort — Most relevant: everything up to (but not including) the “Hoare partition scheme” section.
  • Binary Search — Most relevant: introduction, Algorithm (first procedure), and “Implementation issues.”
• Aho & Ullman: 3.10 - Merge Sort Analysis [PDF]

Supplemental¶

• Section 2 (Quicksort) of “A Guide to Introsort” (Introsort is another algorithm we’ll discuss later)

Levitin¶

• Levitin: 5.0-5.3
  • Divide & Conquer; Master Theorem; Mergesort; Quicksort; Binary Trees

Related¶

• Sorting Algorithms Animations — an excellent resource for visualizing the operation of common sort algorithms; also contains pseudocode and brief highlights of each algorithm.
• The Sound of Sorting — for hearing how a sort algorithm works - it can actually provide some useful insight!