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

I already did, you may want to re-read my comment.



Am I misinterpreting your usage of "best case"?


Without enlightening me on what your interpretation is, I have no way of telling.

pdqsort has a worst case of O(n log n). That means, no matter what, the algorithm never takes more than a constant factor times n log n time to complete.

Since pdqsort is strictly a comparison sort, and comparison sorts can do no better than O(n log n) in the average case, pdqsort is asymptotically optimal in the average case (because the average case can never be worse than the worst case).

On top of the above guarantees, if your input contains only k distinct keys, then pdqsort has a worst case complexity of O(nk). So when k gets small (say, 1-5 distinct elements), pdqsort approaches linear time. That is pdqsort's best case.




Applications are open for YC Summer 2020

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: