' Quicksort with:

' - Uses Rnd to select a random dividing value

' - Stops when there are fewer than CutOff items

' left to sort. It then finishes using

' SelectionSort.

' **************************

Public Sub Quicksort(List() As Long, ByVal min As Long, ByVal max As Long)

Dim med_value As Long

Dim hi As Long

Dim lo As Long

Dim i As Long

' If the list has no more than CutOff elements,

' finish it off with SelectionSort.

If max - min < CutOff Then

Selectionsort List(), min, max

Exit Sub

End If

' Pick the dividing value.

i = Int((max - min + 1) * Rnd + min)

med_value = List(i)

' Swap it to the front.

List(i) = List(min)

lo = min

hi = max

Do

' Look down from hi for a value < med_value.

Do While List(hi) >= med_value

hi = hi - 1

If hi <= lo Then Exit Do

Loop

If hi <= lo Then

List(lo) = med_value

Exit Do

End If

' Swap the lo and hi values.

List(lo) = List(hi)

' Look up from lo for a value >= med_value.

lo = lo + 1

Do While List(lo) < med_value

lo = lo + 1

If lo >= hi Then Exit Do

Loop

If lo >= hi Then

lo = hi

List(hi) = med_value

Exit Do

End If

' Swap the lo and hi values.

List(hi) = List(lo)

Loop

' Sort the two sublists.

Quicksort List(), min, lo - 1

Quicksort List(), lo + 1, max

End Sub