Quick Sort Equal to or Less Than For my course I have to memorise a number of algorithms and to know how to perform them by hand. The steps of the quick sort are given as the following in the text book I am using:


Choose the item at the midpoint of the list to be the first pivot
Write down all the items that are less than the pivot, keeping them in order, in a sub-list
Write down the pivot
Write down the remaining items (those greater than the pivot) in a sub-list
Apply steps 1 to 4 to each sub-list
When all items have been chosen as pivots, stop


The problem is that these instructions are ambiguous as to what to do if there is an item which is equal to the pivot. Does it fall into the first sub-list (written before the pivot) or the second (written after the pivot)? I assume that there is some sort of agreed upon standard for this.
It doesn't really matter which way you decide to break the tightness. You could put all the elements less than or equal to the pivot in the first list and the ones larger than the pivot in the second list, or you could put only the elements smaller than the pivot in the fist list and the ones larger than or equal to the pivot in the second list.

You could even arbitrarily pick the list that will contain an element equal to the pivot (except the pivot itself), on an element-to-element basis. No matter how you will assign these elements to the lists, the algorithm will still work.

Another solution that slightly breaks the algorithm's description you gave is to put all elements smaller than the pivot in the first list $L_1$, all those larger than the pivot in the second list $L_2$, and insert as many copies of the pivot $x$ as there are elements equal to $x$ (including the pivot itself) between the sorted versions of $L_1$ and $L_2$.

As a final note: the pseudocode reported in your textbook seems wrong. You are supposed to recursively repeat the whole procedure on $L_1$ and $L_2$, not just steps $1$ to $4$ (otherwise you will never reach a recursion depth larger than $1$).