Hi, Adam.
That looks very similar to an early version of the qsort that Arthur Knapp and I wrote a couple of years ago. I suppose Arthur got the algorithm from the same source. It sorts the actual list passed to it, rather than leaving it as it is and returning a sorted copy. Some people have said they find this confusing, but we think it’s OK as long as potential users are aware of the fact.
We set out to write the fastest vanilla sort we could and included every AppleScript speed trim we could find. Arthur’s research also turned up the idea of switching to an insertion sort for the “fine tuning”. QuickSort is quite a coarse tool. It’s very effective in the early stages of imposing order on chaos, but as the list becomes more nearly sorted, QuickSort still does a lot of recursing and checking even though it has to move fewer and fewer items around in the list. An insertion sort, on the other hand, while less efficient in the early stages of a sort, does a lot less work when less needs to be done. The sort below stops the QuickSort recursions at levels where 10 or less items need to be sorted, and finishes off with an insertion sort of the entire, nearly-sorted list. On my 2.0 GHz, dual-processor G5, your Qsort sorts a list of 4000 random integers with values between 0 and 10,000 in about 23.5-24.5 seconds. This does the same job in about 0.39 to 0.44 seconds:
13th September 2010: I’ve uploaded a new version of this sort, as part of a collection, to ScriptBuilders.
19th November 2023: ScriptBuilders was discontinued a couple of weeks after I uploaded the collection, so the above links are no longer valid!
on qsort(theList, l, r)
script o
property cutoff : 10
property p : theList
on qsrt(l, r)
set i to l
set j to r
set v to my p's item ((l + r) div 2)
repeat while (j > i)
set u to my p's item i
repeat while (u < v)
set i to i + 1
set u to my p's item i
end repeat
set w to my p's item j
repeat while (w > v)
set j to j - 1
set w to my p's item j
end repeat
if (i > j) then
else
set my p's item i to w
set my p's item j to u
set i to i + 1
set j to j - 1
end if
end repeat
if (j - l < cutoff) then
else
qsrt(l, j)
end if
if (r - i < cutoff) then
else
qsrt(i, r)
end if
end qsrt
on isrt(l, r)
set x to l
set z to l + cutoff - 1
if (z > r) then set z to r
set v to my p's item x
repeat with y from (x + 1) to z
if (my p's item y < v) then
set x to y
set v to my p's item y
end if
end repeat
tell my p's item l
set my p's item l to v
set my p's item x to it
end tell
set u to my p's item (l + 1)
repeat with i from (l + 2) to r
set v to my p's item i
if (v < u) then
set my p's item i to u
repeat with j from (i - 2) to l by -1
if (v < my p's item j) then
set my p's item (j + 1) to my p's item j
else
set my p's item (j + 1) to v
exit repeat
end if
end repeat
else
set u to v
end if
end repeat
end isrt
end script
set listLen to (count theList)
if (listLen > 1) then -- otherwise the handler will error
-- Translate negative indices
if (l < 0) then set l to listLen + l + 1
if (r < 0) then set r to listLen + r + 1
if (r = l) then
-- No point in sorting just one item
else
-- Transpose transposed indices
if (l > r) then
set temp to l
set l to r
set r to temp
end if
if (r - l < o's cutoff) then
-- Skip the Quicksort if cutoff or less items
else
o's qsrt(l, r)
end if
o's isrt(l, r)
end if
end if
return -- nothing
end qsort
-- Demo: sort a list of 4000 integers between 0 and 10,000.
set l to {}
repeat with i from 1 to 4000
set end of my l to random number 10000
end repeat
set t to (GetMilliSec)
qsort(l, 1, -1)
((GetMilliSec) - t) / 1000
Note that, having had more time for development, this handler also allows negative indices for the sort range parameters and the left or the right one can be specified first.
There’s also a CustomQsort version of this, if you’re interested, whose parameters include a script object containing handlers which do the actual comparisons for the sort and return whether one item is “greater” or “less” than the other. This isn’t quite as fast as qsort, but it’s very powerful. Depending on the handlers passed, CustomQsort can sort a list of lists by particular items in the lists, records by particular properties, etc. It can even do reverse sorts.
Later edit:
The main cause of the speed difference between the two handlers appears to be this line in yours:
tell A's L to set {item i, item j} to {item j, item i} -- swap
Apart from the “setting by list”, which detracts slightly from the speed, the ‘tell A’s L’ tells the result of getting the list to change those items. The list-in-a-script-object speed approach needs the reference to be told:
tell (a reference to A's L) to set {item i, item j} to {item j, item i} -- swap