# In place quicksort

I implemented my own sorting in VBA because it doesn't provide its own, and it's healthy to test yourself. It was surprisingly difficult and I ended up make a few tweaks that I didn't expect to make in order for it to sort.

Public Sub quicksort(ByRef arr As Variant, _
ByVal left As Integer, _
ByVal right As Integer)
If right <= left Then Exit Sub  ' length == 1 already sorted
'swap pivot it to end.  I'm not yet concerned about pivot selection
Call swap(arr(CInt((left + right) \ 2)), arr(right))
Dim r As Integer: r = right ' include the pivot in case it's the greatest value
Dim l As Integer: l = left
Dim p As Variant: p = arr(right) ' again pivot is at the end
While l < r
While arr(l) < p And l < r
l = l + 1
Wend
While arr(r) >= p And l < r ' Right claims values which equal pivot
r = r - 1
Wend
If l <> r Then Call swap(arr(l), arr(r))
Wend
' Don't swap the same thing
If l <> right Then Call swap(arr(right), arr(l))
Call quicksort(arr, left, l - 1)
Call quicksort(arr, l + 1, right)
End Sub


VB6/VBA is a "bulky" language to read - If...End If, Sub...End Sub, While...Wend; compared to curly braces languages (Java, C#, etc.), VB6/VBA code, by the nature of its code block delimiters, makes pretty crowded code, even when written cleanly.

Give it some breathing vertical space:

Public Sub QuickSort(arr As Variant, ByVal left As Integer, ByVal right As Integer)

'if length is 1, there's nothing to sort:
If right <= left Or Not IsArray(arr) Then Exit Sub

'swap pivot it to end. I'm not yet concerned about pivot selection
Swap arr((left + right) \ 2), arr(right)

' include the pivot in case it's the greatest value:
Dim r As Integer
r = right

Dim l As Integer
l = left

' pivot is at the end:
Dim p As Variant
p = arr(right)

While l < r

While arr(l) < p And l < r
l = l + 1
Wend

' right claims values equal to pivot:
While arr(r) >= p And l < r
r = r - 1
Wend

If l <> r Then Swap arr(l), arr(r)

Wend

' only swap if values aren't equal:
If l <> right Then Swap arr(right), arr(l)

QuickSort arr, left, l - 1
QuickSort arr, l + 1, right

End Sub


Couple points:

• Unless you have a massive parameters list, keep signatures on a single line.
• Method names should be PascalCase.
• : instruction separator is great for the immediate pane, but should be avoided in actual code - keep it single instruction per line as much as possible.
• Place comments just above the code you're commenting, this makes reading more vertically flowing.
• I don't think CInt cast/conversion is needed here, you're using the \ integer division operator, on two Integer variables - the result has to be an Integer, hence the conversion would be redundant.
• Call is a relic from ancient, stone-tablet-BASIC versions; dropping it allows you to also drop the parentheses that surround the parameters (not dropping the parentheses wouldn't compile).
• @user58697 is correct, the outer While loop could be extracted into its own method.
• What happens if arr isn't an array? I know, dumb edge case, but your method takes a Variant (it has to), and that could be literally anything. Guarding against that dumb error is fairly easy: IsArray(arr) must return True.
• I would avoid chopped-off and single-letter names, especially when they involve a lowercase l:

• arr => items or values
• p => pivotValue
• r => rightIndex
• l => leftIndex

Few notes.

• All algorithms on ranges are much simpler if the range is considered semi-open (that is, right is just beyond the last interesting element.
• The While l < r loop does a very important job; important enough to factor it into a separate function, Public Sub Partition
• One more thing you want to do is to eliminate a last tail-recursive call to quicksort. It is very well possible that the compiler will do it for you; still it is better to be explicit.
• You mean to init r = right - 1? But that breaks if the pivot is the single greatest value. – cheezsteak Apr 18 '14 at 18:32

Just one comment: use Longs instead of Integers, sometimes it causes a dramatic improvement in speed (Excel converts Integers to Longs in the background).