median of three values strategy

by

The median of three has you look at the first, middle and last elements of the array, and choose the median of those three elements as the pivot.

To get the “full effect” of the median of three, it’s also important to sort those three items, not just use the median as the pivot — this doesn’t affect what’s chosen as the pivot in the current iteration, but can/will affect what’s used as the pivot in the next recursive call, which helps to limit the bad behavior for a few initial orderings (one that turns out to be particularly bad in many cases is an array that’s sorted, except for having the smallest element at the high end of the array (or largest element at the low end). For example:

Compared to picking the pivot randomly:

  1. It ensures that one common case (fully sorted data) remains optimal.
  2. It’s more difficult to manipulate into giving the worst case.
  3. A PRNG is often relatively slow.

That second point probably bears a bit more explanation. If you used the obvious (rand()) random number generator, it’s fairly easy (for many cases, anyway) for somebody to arrange the elements so it’ll continually choose poor pivots. This can be a serious concern for something like a web server that may be sorting data that’s been entered by a potential attacker, who could mount a DoS attack by getting your server to waste a lot of time sorting the data. In a case like this, you could use a truly random seed, or you could include your own PRNG instead of using rand() — or you use use Median of three, which also has the other advantages mentioned.

On the other hand, if you use a sufficiently random generator (e.g., a hardware generator or encryption in counter mode) it’s probably more difficult to force a bad case than it is for a median of three selection. At the same time, achieving that level of randomness typically has quite a bit of overhead of its own, so unless you really expect to be attacked in this case, it’s probably not worthwhile (and if you do, it’s probably worth at least considering an alternative that guarantees O(N log N) worst case, such as a merge sort or heap sort.

More Related Contents:

  1. Why is quicksort better than mergesort?
  2. Quicksort: Choosing the pivot
  3. Quicksort vs heapsort
  4. Quicksort superiority over Heap Sort
  5. Sorting (Quicksort) ,Partition
  6. Apply Quicksort to the list M,E,R,G,E,S,O,R,T
  7. What should be the algorithm of the below statement?
  8. Fastest sort of fixed length 6 int array
  9. Is there an O(n) integer sorting algorithm?
  10. Which sort algorithm works best on mostly sorted data? [closed]
  11. Merge Sort a Linked List
  12. Natural Sorting algorithm
  13. Quick sort Worst case
  14. Algorithm to separate items of the same type
  15. Compute the minimal number of swaps to order a sequence
  16. Which parallel sorting algorithm has the best average case performance?
  17. Worst case for QuickSort – when can it occur?
  18. Fast algorithm implementation to sort very small list
  19. Sorting in linear time? [closed]
  20. Quick Sort Vs Merge Sort [duplicate]
  21. What is a bubble sort good for? [closed]
  22. Sorting in place
  23. When is each sorting algorithm used? [closed]
  24. Comparison-based ranking algorithm
  25. Why is bubble sort O(n^2)?
  26. Find the pair across 2 arrays with kth largest sum
  27. Stable separation for two classes of elements in an array
  28. QuickSort and Hoare Partition
  29. Find the k largest elements in order
  30. Why is Insertion sort better than Quick sort for small list of elements?

Leave a Comment