pos the if statement at line of listing is included to prevent swap from occurring when the right marker is at the same position as the pivot value this situation will occur when there are no keys in the list that are smaller than the pivot finallythe function returns the pivot position for use in splitting the sequence into the two segments we are not limited to selecting the first key within the list as the pivotbut it is the easiest to implement we could have chosen the last key instead butin practiceusing the first or last key as the pivot is poor choice especially when subsequence is already sorted that results in one of the segments being empty choosing key near the middle is better choice that can be implemented with few modifications to the code provided we leave these modifications as an exercise efficiency analysis the quick sort algorithm has an average or expected time of ( log nbut runs in ( in the worst casethe analysis of which is left as an exercise even though quick sort is quadratic in the worst caseit does approach the average case in many instances and has the advantage of not requiring additional temporary storage as is the case with the merge sort the quick sort is the commonly used algorithm to implement sorting in language libraries earlier versions of python used quick sort to implement the sort(method of the list structure in the current version of pythona hybrid algorithm that combines the insertion and merge sort algorithms is used instead how fast can we sortthe comparison sort algorithms achieve their goal by comparing the individual sort keys to other keys in the list we have reviewed five sorting algorithms in this and the first three--bubbleselectionand insertion--have worst case time of ( while the merge sort has worst case time of ( log nthe quick sortthe more commonly used algorithm in language librariesis ( in the worst case but it has an expected or average time of ( log nthe natural question is can we do better than ( log )for comparison sortthe answer is no it can be shownwith the use of decision tree and examining the permutations of all possible comparisons among the sort keysthat the worst case time for comparison sort can be no better than ( log nthis does not meanhoweverthat the sorting operation cannot be done faster than ( log nit simply means that we cannot achieve this with comparison sort in the next sectionwe examine distribution sort algorithm that works in linear time distribution sort algorithms use techniques other than comparisons