SUNY Geneseo Department of Computer Science

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

Solution to Lab 6 posted

Questions?

Merge sort?

• Manually execute the algorithm from the text on some data, resulting in...

What if there are an odd number of data items?

• No problem, array simply splits not quite evenly, but this is no problem for the algorithm. Watch It at http://www.geocities.com/SiliconValley/Program/2864/File/Merge1/mergesort.html

Lab

Improve your word-count-by-sorting program to run in O( w logw ) time, where w = total number of words in the document.

Next

Performance of Mergesort

Read section 10.4.3