QuickSort Out Of Stack SpaceI love using QuickSort for doing sorting, but sometimes the recursion can get too much and you get an "out of stack space" error. BubbleSort never has that issue, but it's also a very slow algorithm. Recently I was working on a project where there were serveral documents that had "starting number" and "ending number" values. I wanted to make sure that there were no gaps - if there was an ending number of 100, there had to be a document with a starting number of 101, and so on. (Don't worry about the last value right now - that's not relevant to this tip). The best way to do the comparison was to sort the documents in starting number order and then I could run through them and check if the first document had starting number 1 and the rest of the documents had a starting number 1 higher than the previous ending number.
I had to do this over hundreds of collections. It would run fine using QuickSort for many of the collections, but sometimes it would run out of stack space and I would need to use a more reliable sorting method. I wanted to use the faster sorting when possible and only resort to BubbleSort when needed. Here's what I came up with:
' Do QuickSort if possible. If "out of stack space" then do the slower BubbleSort
On Error 28 Resume Next ' Trap "out of stack space" error
Call QuickSort(startingNums, docs, True)
On Error GoTo BubbleError
On Error 28 GoTo BubbleError ' Resume normal error trapping
If Err = 28 Then
Err = 0 ' Clear the error handler
Call agentLog.Logaction("Out of stack space error. Trying BubbleSort.")
Call BubbleSort(startingNums, docs, True)
The True parameter to the sorting methods are a flag to indicate sorting in ascending order. My sorting subroutines all take an array to be sorted, an optional companion array (I pass in Nothing if there's no companion array) and the ascending/decending flag.
Note that MergeSort is another sorting algorithm, but that also uses recursion, so it's vulnerable to the same "out of stack space" issue.