Posted by: atri | November 7, 2011

## Lect 29: Mergesort Algorithm

In today’s lecture, we solved the recurrence for bounding the run time of the Mergesort algorithm. We then started looking at the basic problem of multiplying two integers. We’ll continue with the latter next lecture (the material is from Sec 5.5 in the book).

Here are pointers to some things I mentioned in class today:

• In class I mentioned that sorting $n$ numbers takes $\Omega(n\log{n})$ time for any comparison based sorting algorihtm. For a proof, here are some lectures notes by Avrim Blum (who is within a 3.5 hour driving radius at CMU). (The document also proves lower bounds for randomized algorithms!)
• Here is a link to the paper with the best known algorithm for integer multiplication (this follow-up paper might also be of interest to you). The algorithm is due to Martin Furer (who is within a 4 hour driving radius at Penn State). In class I mis-stated the result and said that the run time of the algorithm is much close to $O(n)$ than $O(n\log{n})$. Actually the run time is very close to $O(n\log{n})$.

The slides for the lecture have been uploaded.

Below are links to the student blog posts for the lecture: