if [ipivot break look for larger element stop when we reach an element less than pivot since first pass has moved them to the start of for in reversed (range( ))if [jpivot [ ] [ja[ ] [ibreak the additional space complexity is now ( )but the time complexity is ( ) if / and all elements before are greater than [ ]and all elements after are less than [iintuitivelythis approach has bad time complexity because in the first pass when searching for each additional element smaller than the pivot we start from the beginning howeverthere is no reason to start from so far back--we can begin from the last location we advanced to (similar comments hold for the second pass to improve time complexitywe make single pass and move all the elements less than the pivot to the beginning in the second pass we move the larger elements to the end it is easy to perform each pass in single iterationmoving out-of-place elements as soon as they are discovered red white blue range ( def dutch_flag_partition pivot_index )pivot apivot_index first passgroup elements smaller than pivot smaller for in range(len( ))if [ipivot [ ]asmaller asmaller ] [ismaller + second passgroup elements larger than pivot larger len( for in reversed range(len( )))if [ipivot break elif [ipivot [ ]alarger alarger ] [ilarger - the time complexity is (nand the space complexity is ( the algorithm we now present is similar to the one sketched above the main difference is that it performs classification into elements less thanequal toand greater than the pivot in single pass this reduces runtimeat the cost of trickier implementation we do this by maintaining four subarraysbottom (elements less than pivot)middle (elements equal to pivot)unclassifiedand top (elements greater than pivotinitiallyall elements are in unclassified we iterate through elements in unclassifiedand move elements into one of bottommiddleand top groups according to the relative order between the incoming unclassified element and the pivot as concrete examplesuppose the array is currently - - ??? iwhere the pivot is and denotes unclassified elements there are three possibilities for the first unclassified