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.