4 ms·

But only if you can split parts more or less evenly; in other case, numbers go down quickly...

• emmanueloga_ 12y ago
  True, in which case you can take some measures to avoid worst case inputs... I'm thinking randomization in quicksort, for instance.
  • harperlee 12y ago
    I always liked a lot that solution ("adding noise"), it seems very elegant.