Understanding how a quicksort algorithm recurs in VBA

Question

I read this post recently: VBA array sort function? to see if I could get some code to implement a quicksort algorithm in Excel VBA.

I took the following code from the post and implemented it in Excel:

   Public Sub QuickSort(vArray As Variant, inLow As Long, inHi As Long)
  Dim pivot   As Variant
  Dim tmpSwap As Variant
  Dim tmpLow  As Long
  Dim tmpHi   As Long

  tmpLow = inLow
  tmpHi = inHi

  pivot = vArray((inLow + inHi) \ 2)

  While (tmpLow <= tmpHi)
     While (vArray(tmpLow) < pivot And tmpLow < inHi)
        tmpLow = tmpLow + 1
     Wend

     While (pivot < vArray(tmpHi) And tmpHi > inLow)
        tmpHi = tmpHi - 1
     Wend

     If (tmpLow <= tmpHi) Then
        tmpSwap = vArray(tmpLow)
        vArray(tmpLow) = vArray(tmpHi)
        vArray(tmpHi) = tmpSwap
        tmpLow = tmpLow + 1
        tmpHi = tmpHi - 1
     End If
  Wend

  If (inLow < tmpHi) Then QuickSort vArray, inLow, tmpHi
  If (tmpLow < inHi) Then QuickSort vArray, tmpLow, inHi
End Sub

I then ran through it line by line using the F8 key and to my astonishment it repeatedly highlighted the End Sub line, as the last If statement was false, then jumped back to the last If statement wherein the values of tmpLow and inHi had changed!

I'm using the values for the array from this web page to try and match the line by line output given in the first section with the pivot in the middle: https://www.bogotobogo.com/Algorithms/quicksort.php

My implementation matches the web page until the point where the 7 and 5 need to be swapped. At this point the variables have the following values:

inLow = 0
inHi = 2
tmpLow = 2
tmpHi = 0

As you can see, neither of the If statements are true so the line passes to End Sub. If I then press F8 once more, the highlighting jumps UP to the last If statement and the variables now have the values:

inLow = 0
inHi = 4
tmpLow = 3
tmpHi = 2

This happens several times during the complete run of the algorithm. I have never seen this before and can't come up with an explanation of how the code can go up from End Sub and how the variable values can change without any apparent code being executed.

I'd be very grateful for any help clearing this up.

Thanks,

Simon.

Are you aware that the last 2 if statements call the Quicksort Sub recursively? — horst, May 21 '19 at 04:27

score 1 · Accepted Answer · answered May 21 '19 at 07:18

Following code lines are calling the Sub QuickSort recursively:

  If (inLow < tmpHi) Then QuickSort vArray, inLow, tmpHi
  If (tmpLow < inHi) Then QuickSort vArray, tmpLow, inHi

That means it calls the Sub QuickSort from it's own code before it was finished.

If that happens, then a so called call stack is build. This stack holds the prodedures which are called but not finished yet. And it holds the values of the variables at this point.

You can have a look at this call stack using the button ... in Locals window.

Now, if the current running Sub QuickSort gets finished but there are entrys of that Sub in the call stack, then those entrys must be proceed. To do so the process pointer jumps to the code point which had called the Sub recursively. This will be either the line If (inLow < tmpHi) Then QuickSort vArray, inLow, tmpHi or the line If (tmpLow < inHi) Then QuickSort vArray, tmpLow, inHi. Additional all values of variables which also were put into the stack will be restored. Then the stacked Sub runs further on from that point. So on until the stack does not contain Sub QuickSort anymore. This is how recursion works.

Thank you very much, Axel, for your clear and concise response. I'm aware of recursive functions in a mathematical sense but have not studied how they work in code. I wasn't aware of the call stack or the purpose of that button in the Locals Window. All good learning for me. As it happens, for reasons I won't bore you with, I was hoping to write the algorithm 'in line' - that is to say not as a separate function that is called, but as inline code that uses loops to complete the sorting. I obviously need to review that in light of what you've taught me. Regards. — Simon Aldworth, May 22 '19 at 02:25

Understanding how a quicksort algorithm recurs in VBA

1 Answers1