Pseudocode for a recursive quicksort

A recursive quicksort relies on functionality that can partition a list.  The partitioning process is repeated with any sub-list containing more than 1 item, as suggested by the following algorithm.

REPEAT for each partition with > 1 item
        Partition the list
UNTIL all partitions contain only 1 item

The following pseudocode indicates more specifically how this can be achieved.  Its execution is described in detail below.

Sub QuickSort(Data(), Left, Right)

        IF Left < Right THEN
                PivotPosition = Partition(Data, Left, Right)
                QuickSort(Data, Left, PivotPosition – 1)
                QuickSort(Data, PivotPosition + 1, Right)
        END IF

End Sub

This QuickSort procedure is passed 3 parameters when it is first called by another program.  These are the array that needs to be sorted, along with the lower and upper bounds of that array.  The lower and upper bounds are taken to be the starting positions of the left and right pointers.

Firstly, the original list is partitioned into 3 sub-lists by a function with the name ‘Partition‘ .  This function is passed the array and the left and right pointers when it is called.  The Partition function not only partitions the list, but also returns the resting position of the pivot value (which is where the pointers collided).  The resting position of the pivot value can be used to determine the upper bound of the sub-list on the left hand side (PivotPosition – 1), and the lower bound of the sub-list on the right hand side (PivotPosition + 1).

Immediately after the original list has been partitioned, QuickSort calls itself for the first time.  The second invocation is passed PivotPosition – 1 as the third parameter, so this is taken to be the value of the right pointer.  This means that the second invocation is now working on the left hand side sub-list.  The second invocation also calls the partition function, which returns a value of PivotPosition that defines yet another set of sub-lists, and the one on the left is passed to a third invocation of Quicksort.  The recursive calls continue, and successive invocations of QuickSort are added to the call stack, each processing a smaller left hand side sub-list than the previous invocation.  The value of the right pointer continues to shrink until eventually it is no longer bigger than the value of the left pointer, indicating that there are no more left hand side sub-lists containing more than one item that need to be partitioned.

Now, the invocation at the top of the call stack comes to an end, which means the previous invocation can pick up from where it left off, and attempt to process the right hand side of the list defined by the value of PivotPosition that it was passed.  This of course may result in another left hand side sub-list which will be passed to a new invocation of QuickSort.

The call stack will grow and shrink, and grow and shrink, until every piece of the original list has been partitioned, and the data is fully sorted.

Note that during the process, the original array is never actually split.  Successive sub-lists are identified through pointer manipulation alone.  The data is therefore said to be sorted ‘in place’.  This makes the quicksort very efficient in terms of space usage, and therefore one of the preferred methods of sorting large arrays.