CODEWITHSUNDEEP
algorithmsortingdata-structuresquicksort
Tyler.z.yang
Tyler.z.yang

Reputation: 2450

How is The Median of three partitioning in Quick sort improve about 5% efficiency？

Recently I am learning the algorithm. The book is Mark Allen Weiss's "Data Structures and Algorithm Analysis in C".

When I read the Quick Sort Part, the book said the Median of Three Partitioning will improve the Quick Sort effciency for about 5%. Where is the 5% comes from? Could anybody give me a hand?

Upvotes: 3

Views: 663

Answers (1)

Henk Holterman
Henk Holterman

Reputation: 273374

This SO question attributes it to Robert Sedgewick, but without an explanation.

On this page you'll find a discussion of several sorting methods, including quicksort with and without median-of-three.

Below that is a table called 'empirical results' and it's not hard to spot the ~5% improvement. Given the vast complexity of analyzing over all possible inputs I think it's safe to say that Sedgewicks claim is based on measurements too.

Upvotes: 2

Related Questions