3 ms·

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.goo

• ouid 9y ago
  Best case? Give worst and average case when describing complexities.
  • nightcracker 9y ago
    I already did, you may want to re-read my comment.
    • ouid 9y ago
      Am I misinterpreting your usage of "best case"?
      • nightcracker 9y ago
        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.
  • teraflop 9y ago
    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.