Text Only | Text with Attachments

QB64.org Forum

Active Forums => Programs => Topic started by: bplus on November 01, 2021, 08:29:10 am

Title: Recursive Vrs NonRecursive test with Quicksort
Post by: bplus on November 01, 2021, 08:29:10 am
Seeing Sanmayce Quicksort test with my recursive Quicksort I had to try my own test without using the array in the parameters/arguments call, plus in the Discussion Board Recursion topic brought up some ideas from Luke on recursion that I've been curious experimenting with for some time.

So here's my quick test:
Code: QB64: [Select]
  1. _Title "Recursive Vrs NonRecursive test with Quicksort" 'b+ 2021-11-01
  4. ArrayHigh = 100000000
  5. ReDim Shared As _Unsigned _Integer64 n(1 To ArrayHigh), m(1 To ArrayHigh)
  6.  
  7. For i = 1 To ArrayHigh
  8.     n(i) = i
  10. For i = ArrayHigh To 2 Step -1 ' Fisher Yates Shuffle
  11.     Swap n(i), n(Int(Rnd * i) + 1)
  12.     m(i) = n(i) ' copy m off n
  14. Print "Test arrays ready. Testing Recursive QuickSort first."
  15. m(1) = n(1)
  16. T# = Timer(.001)
  17. QuickSort 1, ArrayHigh
  18. QuickSortT# = Timer(.001) - T#
  19. For i = 1 To ArrayHigh
  20.     If n(i) <> i Then Beep: Print "Error in QuickSort array n."
  22. Print "QuickSort checked, QuickSort time was"; QuickSortT#
  23.  
  24. T# = Timer(.001)
  25. Quicksort_QB64
  26. QuicksortQB64T# = Timer(.001) - T#
  27. For i = 1 To ArrayHigh
  28.     If m(i) <> i Then Beep: Print "Error in Quicksort__QB64 array m."
  30. Print "Quicksort_QB64 checked, Quicksort_QB64 time was"; QuicksortQB64T#
  31.  
  32. ' recursive
  33. Sub QuickSort (start As _Unsigned _Integer64, finish As _Unsigned _Integer64)
  34.     Lo = start: Hi = finish
  35.     Middle = n((Lo + Hi) \ 2)
  36.     Do
  37.         Do While n(Lo) < Middle: Lo = Lo + 1: Loop
  38.         Do While n(Hi) > Middle: Hi = Hi - 1: Loop
  39.         If Lo <= Hi Then
  40.             Swap n(Lo), n(Hi)
  41.             Lo = Lo + 1: Hi = Hi - 1
  42.         End If
  43.     Loop Until Lo > Hi
  44.     If Hi > start Then QuickSort start, Hi
  45.     If Lo < finish Then QuickSort Lo, finish
  47.  
  48. ' non recursive
  49. ' ref:  https://rosettacode.org/wiki/Sorting_algorithms/Quicksort#QB64
  50. Sub Quicksort_QB64
  51.     Left = LBound(m)
  52.     Right = UBound(m)
  53.     LeftMargin = Left
  54.     ReDim Stack&&(Left To Right)
  55.     StackPtr = 0
  56.     StackPtr = StackPtr + 1
  57.     Stack&&(StackPtr + LeftMargin) = Left
  58.     StackPtr = StackPtr + 1
  59.     Stack&&(StackPtr + LeftMargin) = Right
  60.     Do 'Until StackPtr = 0
  61.         Right = Stack&&(StackPtr + LeftMargin)
  62.         StackPtr = StackPtr - 1
  63.         Left = Stack&&(StackPtr + LeftMargin)
  64.         StackPtr = StackPtr - 1
  65.         Do 'Until Left >= Right
  66.             Pivot~&& = m((Left + Right) \ 2)
  67.             Indx = Left
  68.             Jndx = Right
  69.             Do
  70.                 Do While (m(Indx) < Pivot~&&)
  71.                     Indx = Indx + 1
  72.                 Loop
  73.                 Do While (m(Jndx) > Pivot~&&)
  74.                     Jndx = Jndx - 1
  75.                 Loop
  76.                 If Indx <= Jndx Then
  77.                     If Indx < Jndx Then Swap m(Indx), m(Jndx)
  78.                     Indx = Indx + 1
  79.                     Jndx = Jndx - 1
  80.                 End If
  81.             Loop While Indx <= Jndx
  82.             If Indx < Right Then
  83.                 StackPtr = StackPtr + 1
  84.                 Stack&&(StackPtr + LeftMargin) = Indx
  85.                 StackPtr = StackPtr + 1
  86.                 Stack&&(StackPtr + LeftMargin) = Right
  87.             End If
  88.             Right = Jndx
  89.         Loop Until Left >= Right
  90.     Loop Until StackPtr = 0
  92.  
  93.  

Nice non recursion code, doing it with your own stack is interesting. I don't suppose there's a way to do a recursive quicksort without need of any parameters to call? Hmm...


EDIT: Dang it! I never use Call this is what I get for copying what I thought was my code from someone else post. :(
EDIT: Fix a labeling if error found in 2nd test.
Title: Re: Recursive Vrs NonRecursive test with Quicksort
Post by: jack on November 01, 2021, 11:36:48 am
bplus, I don't quite agree with your definition of non-recursive
looks like a dirty hack and not a real non-recursive quick-sort, don't know that it's even possible
Title: Re: Recursive Vrs NonRecursive test with Quicksort
Post by: bplus on November 01, 2021, 12:04:01 pm
Quote from: jack on November 01, 2021, 11:36:48 am
bplus, I don't quite agree with your definition of non-recursive
looks like a dirty hack and not a real non-recursive quick-sort, don't know that it's even possible

Hi Jack,

My definition of non recursive subroutine is one that doesn't call itself to do the job. That draws the line pretty clearly to me.

What may be in question is if the non recursive routine (Sanmayce's post at Rosetta Code) is truly in spirit of Quicksort algorithm and I think it works exactly the same using pivots and working left and right sections of pivot with 2 indexes.

What doesn't look real to you? The stack and it's pointer?
Title: Re: Recursive Vrs NonRecursive test with Quicksort
Post by: jack on November 01, 2021, 12:31:49 pm
bplus, you are basically simulating recursion not replacing it
Title: Re: Recursive Vrs NonRecursive test with Quicksort
Post by: Dimster on November 01, 2021, 12:32:17 pm
Hi as well Jack - It does seem natural that recursive means multiple iteration to the same code. So I was looking at it as perhaps a loop in the main program invoking a sub/function multiple times. But as I'm beginning to learn, recursive means a routine CALLING itself. Steve just provided a recursive routine using IF statements which I'm still trying to make fit into the new definition of recursiveness that I'm formulating. I would be interested in what "Recursive" ( in terms of our use of QB64 coding) means to you.
Title: Re: Recursive Vrs NonRecursive test with Quicksort
Post by: bplus on November 01, 2021, 01:10:01 pm
Looking at Wiki article on Quicksort, it is described as recursive. But does that mean it's not a Quicksort routine if not done recursively? I think not.

What I'd really like to see is if anyone can do Quicksort recursively without parameters in the call to itself!

Jack described the non recursive routine as ugly, I agree, recursive routines are much more elegant (unless you try to hack a no parameters routine for Quicksort LOL).
Title: Re: Recursive Vrs NonRecursive test with Quicksort
Post by: TempodiBasic on November 01, 2021, 05:40:06 pm
Hi dear friends

about Quicksort
starting with a unordered finished set of homogeneus values
to get the goal to order this set
 1. pickup a cutoff value
 2. from its left move to right (over) the greater values than it
 3. from its right move to left (under) the smaller values than it
 4. do again this work for subset left and right of this pivot (here it can entry the recursive method in alternative to iterative method)

-------------
about Iterative quicksort routine posted on Rosetta Code  https://rosettacode.org/wiki/Sorting_algorithms/Quicksort#QB64 (https://rosettacode.org/wiki/Sorting_algorithms/Quicksort#QB64)
it uses confounding name of variables but surely it is not an emulation of stack, moreover to be iterative you must keep trace of your pivot values and Left values and Right values to be sure to run code UNTIL all subsets >1 are evaluated and ordered.

So surely in the iterative way you must write the code to keep value of pivot and left margin and right margin around the loop of a single run of Quicksort (the point n°4 of the overtype scheme)
the best choice seems to be the tail that is a LIFO structure.

here some web informations
https://stackoverflow.com/questions/12553238/quicksort-iterative-or-recursive (https://stackoverflow.com/questions/12553238/quicksort-iterative-or-recursive)
https://www.techiedelight.com/iterative-implementation-of-quicksort/ (https://www.techiedelight.com/iterative-implementation-of-quicksort/)
https://www.geeksforgeeks.org/iterative-quick-sort/?ref=lbp (https://www.geeksforgeeks.org/iterative-quick-sort/?ref=lbp)

       Happy study
Title: Re: Recursive Vrs NonRecursive test with Quicksort
Post by: bplus on November 01, 2021, 06:56:46 pm
I don't know if you guys are understanding what I am doing here. It is just a speed test between a Quicksort recursive subroutine versus a very nice non recursive Quicksort routine that does the very same thing only slightly faster and it does it by emulating how a recursive subroutine works with internal stack by providing a sort (no pun intended) of pseudo stack in the non recursive routine.
Title: Re: Recursive Vrs NonRecursive test with Quicksort
Post by: bplus on November 01, 2021, 10:06:33 pm
I did it, created recursive Quicksort routine without parameters! I used a Shared Stack array and Stack pointer. It is the third test added to the other 2:
Code: QB64: [Select]
  1. _Title "Recursive Vrs NonRecursive #2 test with Quicksort" 'b+ 2021-11-01
  2. '2021-11-01 #2 test try a recursive sub wo parameters
  3.  
  5. ReDim Shared As _Unsigned _Integer64 ArrayHigh, StackPt
  6. ArrayHigh = 10000000
  7. ReDim Shared n(1 To ArrayHigh), m(1 To ArrayHigh), o(1 To ArrayHigh)
  8. ReDim Shared Stack(0 To ArrayHigh \ 8)
  9.  
  10. For i = 1 To ArrayHigh
  11.     n(i) = i
  13. For i = ArrayHigh To 2 Step -1 ' Fisher Yates Shuffle
  14.     Swap n(i), n(Int(Rnd * i) + 1)
  15.     m(i) = n(i) ' copy m off n
  16.     o(i) = n(i)
  18. m(1) = n(1)
  19. o(1) = n(1)
  20. Print "Test arrays ready. Testing Recursive QuickSort first."
  21.  
  22. T# = Timer(.001)
  23. QuickSort 1, ArrayHigh
  24. QuickSortT# = Timer(.001) - T#
  25. For i = 1 To ArrayHigh
  26.     If n(i) <> i Then Beep: Print "Error in QuickSort array n."
  28. Print "QuickSort checked, QuickSort time was"; QuickSortT#
  29.  
  30. T# = Timer(.001)
  31. Quicksort_QB64
  32. QuicksortQB64T# = Timer(.001) - T#
  33. For i = 1 To ArrayHigh
  34.     If m(i) <> i Then Beep: Print "Error in Quicksort__QB64 array m."
  36. Print "Quicksort_QB64 checked, Quicksort_QB64 time was"; QuicksortQB64T#
  37.  
  38. T# = Timer(.001)
  39. StackPt = StackPt + 1
  40. Stack(StackPt) = 1
  41. StackPt = StackPt + 1
  42. Stack(StackPt) = ArrayHigh
  43. QSort
  44. QSortT# = Timer(.001) - T#
  45. For i = 1 To ArrayHigh
  46.     If o(i) <> i Then Beep: Print "Error in QSort array o."
  48. Print "QSort checked, QSort time was"; QSortT#
  49.  
  50. ' recursive
  51. Sub QuickSort (start As _Unsigned _Integer64, finish As _Unsigned _Integer64)
  52.     Lo = start: Hi = finish
  53.     Middle = n((Lo + Hi) \ 2)
  54.     Do
  55.         Do While n(Lo) < Middle: Lo = Lo + 1: Loop
  56.         Do While n(Hi) > Middle: Hi = Hi - 1: Loop
  57.         If Lo <= Hi Then
  58.             Swap n(Lo), n(Hi)
  59.             Lo = Lo + 1: Hi = Hi - 1
  60.         End If
  61.     Loop Until Lo > Hi
  62.     If Hi > start Then QuickSort start, Hi
  63.     If Lo < finish Then QuickSort Lo, finish
  65.  
  66. ' non recursive
  67. ' ref:  https://rosettacode.org/wiki/Sorting_algorithms/Quicksort#QB64
  68. Sub Quicksort_QB64
  69.     Left = LBound(m)
  70.     Right = UBound(m)
  71.     LeftMargin = Left
  72.     ReDim Stack&&(Left To Right)
  73.     StackPtr = 0
  74.     StackPtr = StackPtr + 1
  75.     Stack&&(StackPtr + LeftMargin) = Left
  76.     StackPtr = StackPtr + 1
  77.     Stack&&(StackPtr + LeftMargin) = Right
  78.     Do 'Until StackPtr = 0
  79.         Right = Stack&&(StackPtr + LeftMargin)
  80.         StackPtr = StackPtr - 1
  81.         Left = Stack&&(StackPtr + LeftMargin)
  82.         StackPtr = StackPtr - 1
  83.         Do 'Until Left >= Right
  84.             Pivot~&& = m((Left + Right) \ 2)
  85.             Indx = Left
  86.             Jndx = Right
  87.             Do
  88.                 Do While (m(Indx) < Pivot~&&)
  89.                     Indx = Indx + 1
  90.                 Loop
  91.                 Do While (m(Jndx) > Pivot~&&)
  92.                     Jndx = Jndx - 1
  93.                 Loop
  94.                 If Indx <= Jndx Then
  95.                     If Indx < Jndx Then Swap m(Indx), m(Jndx)
  96.                     Indx = Indx + 1
  97.                     Jndx = Jndx - 1
  98.                 End If
  99.             Loop While Indx <= Jndx
  100.             If Indx < Right Then
  101.                 StackPtr = StackPtr + 1
  102.                 Stack&&(StackPtr + LeftMargin) = Indx
  103.                 StackPtr = StackPtr + 1
  104.                 Stack&&(StackPtr + LeftMargin) = Right
  105.             End If
  106.             Right = Jndx
  107.         Loop Until Left >= Right
  108.     Loop Until StackPtr = 0
  110.  
  111. ' recursive No Parameters!!!
  112. Sub QSort
  113.     If StackPt > 0 Then 'else done!
  114.         finish = Stack(StackPt) 'pull off last 2 arguments
  115.         StackPt = StackPt - 1
  116.         start = Stack(StackPt)
  117.         StackPt = StackPt - 1
  118.  
  119.         Lo = start: Hi = finish
  120.         Middle = o((Lo + Hi) \ 2)
  121.         Do
  122.             Do While o(Lo) < Middle: Lo = Lo + 1: Loop
  123.             Do While o(Hi) > Middle: Hi = Hi - 1: Loop
  124.             If Lo <= Hi Then
  125.                 Swap o(Lo), o(Hi)
  126.                 Lo = Lo + 1: Hi = Hi - 1
  127.             End If
  128.         Loop Until Lo > Hi
  129.  
  130.         If Hi > start Then
  131.             StackPt = StackPt + 1
  132.             Stack(StackPt) = start
  133.             StackPt = StackPt + 1
  134.             Stack(StackPt) = Hi
  135.             QSort
  136.         End If
  137.         If Lo < finish Then
  138.             StackPt = StackPt + 1
  139.             Stack(StackPt) = Lo
  140.             StackPt = StackPt + 1
  141.             Stack(StackPt) = finish
  142.             QSort
  143.         End If
  144.     End If
  146.  
  147.  
  148.  

Surprise! It turns out that it takes longer to play with a pseudo stack loading and resetting pointer than it does to call the Quicksort routine with parameters, a fairly significant amount of time longer.
Title: Re: Recursive Vrs NonRecursive test with Quicksort
Post by: Sanmayce on November 04, 2021, 03:43:09 pm
Thank you @bplus for your tests.
In the morning did write the 'Magnetica' partitioning, which helps greatly in "few distinct keys" scenario, usually 15x to 3x speed boost it gives. However, it hurts speed badly (2x) in "many distinct keys", the problem lies in STILL not well written right part traversal (Jndx), doing unnecessary swaps has to be fixed...
Your test (modified) is given below with ability (just change line 8) to run in "few distinct keys", otherwise it is the most common "many distinct keys":

 


"few distinct keys" scenario:

 


Code: QB64: [Select]
  1. _Title "Recursive Vrs NonRecursive test with Quicksort" 'b+ 2021-11-01, Sanmayce added some stuff 2021-Nov-04
  4. ArrayHigh = 10000000
  5. ReDim Shared As _Unsigned _Integer64 n(1 To ArrayHigh), m(1 To ArrayHigh), z(1 To ArrayHigh)
  6.  
  7. For i = 1 To ArrayHigh
  8.     n(i) = i '13 'i
  10. For i = ArrayHigh To 2 Step -1 ' Fisher Yates Shuffle
  11.     Swap n(i), n(Int(Rnd * i) + 1)
  12.     m(i) = n(i) ' copy m off n
  13.     z(i) = n(i) ' copy m off n
  15. Print "Test arrays ready. Testing Recursive QuickSort first."
  16. n(1) = ArrayHigh
  17. m(1) = n(1)
  18. z(1) = n(1)
  19.  
  20. T# = Timer(.001)
  21. QuickSort 1, ArrayHigh
  22. QuickSortT# = Timer(.001) - T#
  23. For i = 1 To ArrayHigh - 1
  24.     If n(i) > n(i + 1) Then Print "NOT OK!": End
  26. Print "QuickSort checked, QuickSort time was"; QuickSortT#
  27.  
  28.  
  29. T# = Timer(.001)
  30. Quicksort_QB64
  31. QuicksortQB64T# = Timer(.001) - T#
  32. For i = 1 To ArrayHigh - 1
  33.     If m(i) > m(i + 1) Then Print "NOT OK!": End
  35. Print "Quicksort_QB64 checked, Quicksort_QB64 time was"; QuicksortQB64T#
  36.  
  37.  
  38. T# = Timer(.001)
  39. Quicksort_QB64_v2
  40. QuicksortQB64T# = Timer(.001) - T#
  41. For i = 1 To ArrayHigh - 1
  42.     If z(i) > z(i + 1) Then Print "NOT OK!": End
  44. Print "Quicksort_QB64_v2 checked, Quicksort_QB64_v2 time was"; QuicksortQB64T#
  45.  
  46.  
  47.  
  48. ' recursive
  49. Sub QuickSort (start As _Unsigned _Integer64, finish As _Unsigned _Integer64)
  50.     Lo = start: Hi = finish
  51.     Middle = n((Lo + Hi) \ 2)
  52.     Do
  53.         Do While n(Lo) < Middle: Lo = Lo + 1: Loop
  54.         Do While n(Hi) > Middle: Hi = Hi - 1: Loop
  55.         If Lo <= Hi Then
  56.             Swap n(Lo), n(Hi)
  57.             Lo = Lo + 1: Hi = Hi - 1
  58.         End If
  59.     Loop Until Lo > Hi
  60.     If Hi > start Then QuickSort start, Hi
  61.     If Lo < finish Then QuickSort Lo, finish
  63.  
  64. ' non recursive
  65. ' ref:  https://rosettacode.org/wiki/Sorting_algorithms/Quicksort#QB64
  66. Sub Quicksort_QB64
  67.     Left = LBound(m)
  68.     Right = UBound(m)
  69.     LeftMargin = Left
  70.     ReDim Stack&&(Left To Right)
  71.     StackPtr = 0
  72.     StackPtr = StackPtr + 1
  73.     Stack&&(StackPtr + LeftMargin) = Left
  74.     StackPtr = StackPtr + 1
  75.     Stack&&(StackPtr + LeftMargin) = Right
  76.     Do 'Until StackPtr = 0
  77.         Right = Stack&&(StackPtr + LeftMargin)
  78.         StackPtr = StackPtr - 1
  79.         Left = Stack&&(StackPtr + LeftMargin)
  80.         StackPtr = StackPtr - 1
  81.         Do 'Until Left >= Right
  82.             Pivot~&& = m((Left + Right) \ 2)
  83.             Indx = Left
  84.             Jndx = Right
  85.             Do
  86.                 Do While (m(Indx) < Pivot~&&)
  87.                     Indx = Indx + 1
  88.                 Loop
  89.                 Do While (m(Jndx) > Pivot~&&)
  90.                     Jndx = Jndx - 1
  91.                 Loop
  92.                 If Indx <= Jndx Then
  93.                     If Indx < Jndx Then Swap m(Indx), m(Jndx)
  94.                     Indx = Indx + 1
  95.                     Jndx = Jndx - 1
  96.                 End If
  97.             Loop While Indx <= Jndx
  98.             If Indx < Right Then
  99.                 StackPtr = StackPtr + 1
  100.                 Stack&&(StackPtr + LeftMargin) = Indx
  101.                 StackPtr = StackPtr + 1
  102.                 Stack&&(StackPtr + LeftMargin) = Right
  103.             End If
  104.             Right = Jndx
  105.         Loop Until Left >= Right
  106.     Loop Until StackPtr = 0
  108.  
  109.  
  110. Sub Quicksort_QB64_v2
  111.     Left = LBound(z)
  112.     Right = UBound(z)
  113.     ReDim Stack&&(Left To Right)
  114.     StackPtr = 0
  115.     StackPtr = StackPtr + 1
  116.     Stack&&(StackPtr + LeftMargin) = Left
  117.     StackPtr = StackPtr + 1
  118.     Stack&&(StackPtr + LeftMargin) = Right
  119.     Do 'Until StackPtr = 0
  120.         Right = Stack&&(StackPtr)
  121.         Left = Stack&&(StackPtr - 1)
  122.         StackPtr = StackPtr - 2
  123.         Do 'Until Left >= Right
  124.  
  125.             ' 'Classica' partitioning [
  126.             'Pivot~&& = z((Left + Right) \ 2)
  127.             'Indx = Left
  128.             'Jndx = Right
  129.             'Do
  130.             '    Do While (z(Indx) < Pivot~&&)
  131.             '        Indx = Indx + 1
  132.             '    Loop
  133.             '    Do While (z(Jndx) > Pivot~&&)
  134.             '        Jndx = Jndx - 1
  135.             '    Loop
  136.             '    If Indx <= Jndx Then
  137.             '        If Indx < Jndx Then Swap z(Indx), z(Jndx)
  138.             '        Indx = Indx + 1
  139.             '        Jndx = Jndx - 1
  140.             '    End If
  141.             'Loop While Indx <= Jndx
  142.             ' 'Classica' partitioning ]
  143.  
  144.             ' 'Magnetica' partitioning [
  145.             Jndx = Right
  146.             PL = Left
  147.             PR = Left
  148.             Swap z((Left + Right) \ 2), z(PL)
  149.             Do While PR < Jndx
  150.                 If z(PR) > z(PR + 1) Then
  151.                     Swap z(PL), z(PR + 1)
  152.                     PL = PL + 1
  153.                     PR = PR + 1
  154.                 ElseIf z(PR) = z(PR + 1) Then
  155.                     PR = PR + 1
  156.                 Else '<
  157.                     Swap z(PR + 1), z(Jndx)
  158.                     Jndx = Jndx - 1
  159.                 End If
  160.             Loop
  161.             Jndx = PL - 1
  162.             Indx = PR + 1
  163.             ' 'Magnetica' partitioning ]
  164.  
  165.             If Indx < Right Then
  166.                 StackPtr = StackPtr + 2
  167.                 Stack&&(StackPtr - 1) = Indx
  168.                 Stack&&(StackPtr) = Right
  169.             End If
  170.             Right = Jndx
  171.         Loop Until Left >= Right
  172.     Loop Until StackPtr = 0
  174.  

Consider having two records/fields (list of all living 7 billion people names with their birth date), now, the second column/field if it is to be sorted we cannot afford using the "Classica" partitioning because we enter the "few distinct keys" scenario with some 100 unique values. I am against "patches" of some pseudo-smart heuristics trying  to adapt "on the fly" to the type of keys in use, rather, I would prefer having two dedicated subroutines, one dealing with "few" the other with "many".
Of course if we can come up with fixing the "Magnetica" then there will be one subroutine only, nice and dirty-cheap, heh-heh.

Also, very often one needs sorting all the files on some drive by their year, not a good feeling 'Classica' to force you wait  7 seconds as in example above for 10,000,000 files.
In practice, there are more brutal sort cases, such as sorting occurrences of 600 billion English 5-grams (phrases of 5 words), the nasty 600GB x 4bytes =~2TB.

You are right @jack, but there is one aspect you should consider, being dirty from what standpoint!
As far as I know, using runtime stack (in addition to program's needs) is not a good practice, saw few discussions in the past where some Linux kernel gurus explicitly stated recursive code is not welcome at all, the topic was some very refined B-tree implementation, but recursive. Simply, the stack is considered an internal zone, endangered in case of entering deep recursion or for some reason stack being used extensively to the brim, hah-hah, hence the super popular stackoverflow site.

Oof, forgot to share the benchmarks done on some modern machines:
https://www.overclock.net/threads/benchmark-quicksort-says-sorting-2-billion-qwords.1794855/
Text Only | Text with Attachments