so have array {3,1,4,1,5,9,2,6,5,3,5}
i'm using median-of-three method pivots.
so in case median here between left, middle, right: 3,9,5. it's 5
first thing make sure pivot on leftmost. keep numbers less 5 in left , move numbers greater right of array. final result is: {3,1,4,1,2,3|5|5,9,6,5}
now quicksort left , right subarrays.
{3,1,4,1,2,3} has median 3 , after rearranging {1,1,2,3,4}
{5,9,6,5} has median 5 , {5,5,9,6} result of sorting equal , greater numbers right. subarray didn't sort first subarray. work if median 6. did going wrong? thanks.
you have sort right subarray of {|5|5,9,6} (or {5|5|,9,6}) again. median 6 , result {5,6,9} (or {6,9}).
also note naive quicksort many duplicate keys can degrade quadratic time complexity. there ways detect keys equal pivot , exclude them subarrays sorted recursively.
