Hacker News new | ask | show | jobs
by wiz21c 3281 days ago
Is there a analysis of its complexity ? The algorithm looks very nice !
1 comments

Hey, author of pdqsort here, the draft paper contains complexity proofs of the O(n log n) worst case and O(nk) best case with k distinct keys: https://drive.google.com/open?id=0B1-vl-dPgKm_T0Fxeno1a0lGT0...
Best case? Give worst and average case when describing complexities.
There's not much value in discussing the asymptotic worst-case or average-case performance of sorting algorithms, because just about every algorithm worth talking about is already optimal in that regard.

The interesting performance differences are all about constant factors.

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.