As in quickselect, there is a subprocedure called that can, in linear time, group a list (ranging from indices left to right) into two parts, those less than a certain element, and those greater than or equal to the element.
function partition(list, left, right, pivotIndex) pivotValue := list[pivotIndex] swap list[pivotIndex] and list[right] // Move pivot to end storeIndex := left for i from left to right-1 if list[i] < pivotValue swap list[storeIndex] and list[i] increment storeIndex swap list[right] and list[storeIndex] // Move pivot to its final place return storeIndex .