What if you always recurse into the smaller half, and use tail-recursion/looping... | Hacker News

Hacker News new | past | comments | ask | show | jobs | submit

login

eutectic on Nov 21, 2016 | parent | context | favorite | on: Inspecting C's qsort Through Animation

What if you always recurse into the smaller half, and use tail-recursion/looping to process the rest? Doesn't that keep the space usage bounded to O(log(n))?

deathanatos on Nov 21, 2016 [–]

This is correct, and is noted in the Wikipedia article's discussion of memory usage[1].

(Which I was only reading because I was erroneously thinking that quicksort was O(1) memory – I was completely forgetting stack space.)

[1]: https://en.wikipedia.org/wiki/Quicksort#Space_complexity

Consider applying for YC's Spring batch! Applications are open till Feb 11.
Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact