Hacker News
new
|
past
|
comments
|
ask
|
show
|
jobs
|
submit
login
zahlman
3 months ago
|
parent
|
context
|
favorite
| on:
Quicksort explained IKEA-style
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)?
Dwedit
3 months ago
|
next
[–]
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...
enedil
3 months ago
|
prev
[–]
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).
Guidelines
|
FAQ
|
Lists
|
API
|
Security
|
Legal
|
Apply to YC
|
Contact
Search:
