3 ms·

if you have decent (randomized) pivoting, you never hit the worst case or anything like it

• SkiFire13 3mo ago
  You don't need randomized pivoting for this, there are deterministic ones like median of median that will also result in a O(nlogn) worst case. Also note that with a randomized pivoting you _might_ hit a O(n^2) worst case, it's just that it's incredibly rare and cannot be forced by an attacker controlling your input, so for most practical purposes can be ignored.
  • adgjlsfhk1 3mo ago
    median of median does give you guarenteed n*log(n) but it doubles your memory reads per pass making it pretty poor. single random is almost guarenteed to take fewer passes (and median of 3-7 random values can make the number of extra passes over the minimum to be very low)
    • SkiFire13 3mo ago
      You don't have to use median of medians for every pass, you can use it only when you detect that each pass is not making enough progress, i.e. when you hit the worst case.