3 ms·

I don't see why quick sort with a random pivot takes a non deterministic amount of time.

• rdtsc 10y ago
  > I don't see why quick sort with a random pivot takes a non deterministic amount of time. Because it might sort faster or slower depending on how the pivot gets picked. But you'd get the sorted list in the end. A Monte Carlo solution might run for 5 seconds but you might get a partially sorted list only.
  • tgb 10y ago
    Ah I see thanks. I was thinking the claim was that it might take an unbounded amount of time.