Tuesday, March 2, 2010

Quicksort worst-case

Traditionally quicksort is considered quadratic in the worst case. there is a randomized version which makes it O(n log n). Do you know how to make it O(n log n) worst case without using randomization?

2 comments:

  1. Pivot Element selected as median of first element, last element, & the middle element

    ReplyDelete
  2. Introsort per your earlier posting

    http://codingplayground.blogspot.com/2009/03/introsort-mixing-two-words-quicksort.html

    ReplyDelete