Recursive QuickSort

The following QuickSort algorithm for sorting arrays is taken directly from the SORTDEMO program, with only slight modifications to make it more modular and to accommodate differences between Visual Basic and QuickBasic:

‘ Recursive QuickSort algorithm
Sub SortArrayRec(aTarget() As Variant, _
                 Optional vFirst As Variant, Optional vLast As Variant, _
                 Optional helper As ISortHelper)
    Dim iFirst As Long, iLast As Long
    If IsMissing(vFirst) Then iFirst = LBound(aTarget) Else iFirst = vFirst
    If IsMissing(vLast) Then iLast = UBound(aTarget) Else iLast = vLast
    If helper Is Nothing Then Set helper = New CSortHelper
    
With helper
    If iFirst < iLast Then

        ‘ Only two elements in this subdivision; exchange if
        ‘ they are out of order, and end recursive calls
        If iLast - iFirst = 1 Then
            If .Compare(aTarget(iFirst), aTarget(iLast)) > 0 Then
                .Swap aTarget(iFirst), aTarget(iLast)
            End If
        Else

            Dim iLo As Long, iHi As Long
            ‘ Pick pivot element at random and move to end
            .Swap aTarget(iLast), aTarget(MRandom.Random(iFirst, iLast))
            iLo = iFirst: iHi = iLast
            Do

                ‘ Move in from both sides toward pivot element
                Do While (iLo < iHi) And _
                         .Compare(aTarget(iLo), aTarget(iLast)) <= 0
                    iLo = iLo + 1
                Loop
                Do While (iHi > iLo) And _
                         .Compare(aTarget(iHi), aTarget(iLast)) >= 0
                    iHi = iHi - 1
                Loop

                ‘ If you haven’t reached pivot element, it means
                ‘ that two elements on either side are out of
                ‘ order, so swap them
                If iLo < iHi Then .Swap aTarget(iLo), aTarget(iHi)
            Loop While iLo < iHi

            ‘ Move pivot element back to its proper place
            .Swap aTarget(iLo), aTarget(iLast)

            ‘ Recursively call SortArrayRec (pass smaller
            ‘ subdivision first to use less stack space)
            If (iLo - iFirst) < (iLast - iLo) Then
                SortArrayRec aTarget(), iFirst, iLo - 1, helper
                SortArrayRec aTarget(), iLo + 1, iLast, helper
            Else
                SortArrayRec aTarget(), iLo + 1, iLast, helper
                SortArrayRec aTarget(), iFirst, iLo - 1, helper
            End If
        End If
    End If
End With
End Sub

For the moment, ignore the helper object parameter and concentrate on the algorithm. QuickSort works on the divide-and-conquer principle. It splits the array into two groups and then sorts both the top and the bottom. It does this by calling itself to sort each group. Recursion makes QuickSort intelligible but also subjects it to stack limitations. A recursive algorithm has the potential to run out of stack space as it pushes more arguments and local variables onto the stack each time it calls itself.