CODEWITHSUNDEEP
algorithmsortingselectionquicksort
kjh
kjh

Reputation: 3411

If the median of medians algorithm doesn't change the avg-case complexity of quicksort, why use it?

Given the hard lower bound on the sorting algorithm's average case complexity Omega(n*lg(n)), when/why would you decide to spend the time implementing this selection algorithm with quicksort rather than just using a random pivot or just the simple (n/2)th position in the array?

Upvotes: 3

Views: 468

Answers (1)

samgak
samgak

Reputation: 24427

Because it has a better worst-case time complexity.

The approximate median-selection algorithm can also be used as a pivot strategy in quicksort, yielding an optimal algorithm, with worst-case complexity O(n log n). Although this approach optimizes quite well, it is typically outperformed in practice by instead choosing random pivots, which has average linear time for selection and average log-linear time for sorting, and avoids the overhead of computing the pivot. Median of medians is used in the hybrid introselect algorithm as a fallback, to ensure worst-case linear performance: introselect starts with quickselect, to obtain good average performance, and then falls back to median of medians if progress is too slow.

Upvotes: 3

Related Questions