Public Module quicksort
    Public Sub quicksort(ByRef A As List(Of iQuicksortable))
        qsort(A, 0, A.Count - 1)
    End Sub

    Private Sub qsort(ByRef A As List(Of iQuicksortable), lo As Integer, hi As Integer)
        If lo < hi Then
            Dim p As Integer = partition(A, lo, hi)     'run partition and get index of pivot
            qsort(A, lo, p - 1)         '-1 because pivot was at p and can be excluded
            qsort(A, p + 1, hi)         '+1 because pivot was at p and can be excluded
        End If
    End Sub

    Private Function partition(ByRef A As List(Of iQuicksortable), lo As Integer, hi As Integer) As Integer
        'lo is the index of the leftmost element
        'hi is the (inclusive) index of the rightmost element
        Dim pivotIndex As Integer = choosePivot(A, lo, hi)
        Dim pivotValue As Integer = A(pivotIndex).qsValue


        'put pivot at A(hi)
        swap(A, pivotIndex, hi)
        Dim storeIndex As Integer = lo


        'compare each value between A(lo) and A(hi) with pivot
        For i = lo To hi - 1                    '-1 because pivot is at A(hi)
            If A(i).qsValue <= pivotValue Then
                swap(A, i, storeIndex)
                storeIndex += 1
            End If
        Next


        'move pivot to final place
        swap(A, storeIndex, hi)


        'return index of pivot's final place
        Return storeIndex
    End Function

    Private Sub swap(ByRef A As List(Of iQuicksortable), p1 As Integer, p2 As Integer)
        If p1 = p2 Then Exit Sub

        Dim tempValue As iQuicksortable = A(p1)
        A(p1) = A(p2)
        A(p2) = tempValue
    End Sub

    Private Function choosePivot(ByRef A, p1, p2) As Integer
        Return CInt(Math.Abs(p2 - p1) / 2)
    End Function
End Module

Public Interface iQuicksortable
    Property qsValue As Integer
End Interface