undefined | Better HN

0 pointszahlman9mo ago0 comments

Am I alone in that I always felt like mergesort was easier to explain (and the O(n lg n) behaviour was easier to prove)?

0 comments

2 comments · 2 top-level

Dwedit9mo ago

Merge Sort is much easier to explain when you do the non-recursive version that's upside-down. Merge size 1 together, merge size 2 together, merge size 4 together, merge size 8 together, etc...

enedil9mo ago

O(n lg n) is indeed hard to prove for quicksort, because it is not even true in the general case. Worst case is O(n^2).

j / k navigate · click thread line to collapse