SUNY Geneseo Department of Computer Science

Performance of Mergesort

Return to List of Lectures

Misc

Hour Exam 2

• Monday, April 2
• Covers material since exam 1 (e.g., loop invariants, correctness and performance analysis of loops, sorting)
• Similar in style and rules to exam 1

Hand out Lab 9

Most and Least Swaps contest in Lab 8

• Least: Aaron, Chris, Christian, Takumi, with 0
• Most: Christian, with 24
• Why did an already-sorted array produce the fewest swaps, when it's supposed to be a worst case?
  • Swaps aren't what's counted
  • Comparisons are counted
  • Worst-case number of comparisons = Θ(n²)
  • This overwhelms good effects of small numbers of swaps

Questions?

Mergesort Performance

Section 10.4.3

• Different cases for Mergesort, counting comparisons
  • Find pattern
  • Calculate asymptotic runtime
• Best case
  • Same as worst case
  • n logn
• Worst case
• Mergesort beats Quicksort in worst case, but worst case for Quicksort isn't all that likely

Derivations of best (or worst) case via Master Theorem

• Best case
  • C(n) = n/2 + 2 C(n/2)
  • g(n) = n/2 = Θ(n)
  • a = b = 2, log_ba = log₂2 = 1
  • n^log₂2 = n
  • Θ( n^log₂2 logn ) = Θ( n logn )
• Worst case
  • C(n) = (n-1) + 2 C(n/2)
  • a, b same as above, g(n) asymptotically the same
  • Also, same recurrence as Quicksort's best case
• Hand out Problem Set 11

Another Way of Defining Mergesort

• http://math.hws.edu/TMCM/java/xSortLab/
• "Straight Mergesort," iterative

Next

Introduction to searching

(No reading!)