The efficiency of quick sort depends upon the selection of pivot. The pivot can bifurcate the list
into compartments. Sometimes, the compartments are having the same sizes or dissimilar sizes.
Assume a case in which pivot is at middle. Thus, the total elements towards lift of it and right are
equal.
We can express the size of list with the power of 2. The mathematical representation for the size
is n-2s. The value of s can be calculated as log2 n.
After the first pass is completed there will be two compartments having equal number of elements
that is, m/2 elements are on the left side as w
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month, and much more.