How does the improved basic QuickSort gets speedier? I compiled stats for comparison to pivot and swapped items for lists of 10, 100, 1000, 10,000 and 100,000 items. I did the same with the almost sorted lists (2 items swapped). Here are the results:
QuickSortImprovedStats.pdf (44.0 KB)
Hi @jean.o.matic.
On my machine, it’s your first Quicksort script above that’s two or three times as fast as the second, not the other way round.
The first appears to be a paraphrase of one of my own efforts. 
It contains these obsessive optimisations:
Individually, these optimisations are minuscule in effect. But the thousands of times they’re executed in a sort can add up.
Thanks Nigel,
The 1st one I posted is the IMPROVED basic Quicksort. I did not want to use the word OPTIMIZED since I am not using techniques like 3-point pivot ot cutoffs to switch to another algorithm It is derived from a version I found somewhere on the web, saved not tested and forgotten until last year. It is in now the one and only in my script library. I modified it to use your CompObject script to handle various comparison possibilities in lists, lists of lists, lists of records…
The second one is the basic Quicksort I picked from this website a very long time ago. It served me well as I have rarely lists longer than 500 items in my scripts. It could have been posted by Adam Bell, not sure.
I wanted to show that for most uses, an in-place recursive Quicksort can be very efficient. Also that AppleScript handles recursion very well.
Did you have chance to have a look at new sort algorithms like timsort, pdqsort. fluxsort or the latest and greatest glidesort?
I could not find pseudo-code for glidesort.
in rust (yikes!), with presentation:
It seems to that where this work gets really useful and unique is when it allows the sorting of groups of values, as in Nigel’s slave sort.
If one needs to sort lists of numbers or characters or strings, the sorts available through the foundation framework are probably faster than anything written in Applescript.
But when I need to sort a list of image descriptors, EG {Image_ID, Image_Name, Image_Path} (part of a search for image references with invalid paths), that is where these custom search algorithms becomecreally useful.
Hi @jean.o.matic.
I did have a go at timsort eight years ago, but I’m not sure how close I got to Peters’s intentions as there was only his verbal description to go on. I see from my notes in the topic where I posted it that my implementation worked OK, but could only keep up with my own iterative ternary merge sort (posted in the same topic) when the lists were already largely sorted. I doubt I could rewrite either of them from scratch now! 
Just to set a baseline, I wrote an ASObjC solution using the example contained in jean.o.matic’s post 14. The timing result for the ASObjC solution was 8 milliseconds, and the results for jean.o.matic’s AppleScript in post 14 and Nigel’s AppleScript in post 19 were 138 and 55 milliseconds, respectively. The timing results for the ASObjC solution assumes that the Foundation framework is in memory, which is almost always the case on my computer. If that’s not the case, the time it takes to load the framework is about 250 milliseconds.
use framework "Foundation"
use scripting additions
-- untimed code
set theList to {}
repeat 10000 times
set the end of theList to random number from 1 to 10000
end repeat
-- start time
set startTime to current application's CACurrentMediaTime()
-- timed code
set theArray to current application's NSArray's arrayWithArray:theList
set sortedList to (theArray's sortedArrayUsingSelector:"compare:") as list
-- elapsed time
set elapsedTime to (current application's CACurrentMediaTime()) - startTime
set numberFormatter to current application's NSNumberFormatter's new()
(numberFormatter's setFormat:"0")
set elapsedTime to ((numberFormatter's stringFromNumber:(elapsedTime * 1000)) as text) & " milliseconds"
-- result
elapsedTime -->8 milliseconds
# count sortedList -->10000
# sortedList --script works as expected
The primary focus of this thread is sorting very-large lists, If the list will never contain more than say 50 items, a bubble sort is fast and involves little code.
use framework "Foundation"
use scripting additions
--untimed code
set theList to {}
repeat 50 times
set the end of theList to random number from 1 to 50
end repeat
--start time
set startTime to current application's CACurrentMediaTime()
--timed code
repeat with i from (count theList) to 2 by -1
repeat with j from 1 to i - 1
if item j of theList > item (j + 1) of theList then
set {item j of theList, item (j + 1) of theList} to {item (j + 1) of theList, item j of theList}
end if
end repeat
end repeat
--elapsed time
set elapsedTime to (current application's CACurrentMediaTime()) - startTime
set numberFormatter to current application's NSNumberFormatter's new()
(numberFormatter's setFormat:"0")
set elapsedTime to ((numberFormatter's stringFromNumber:(elapsedTime * 1000)) as text) & " milliseconds"
--result
elapsedTime --6 milliseconds
# count theList -->50
# theList --sorts as expected
The test computer was an M6 Mac mini running macOS Golden Gate.
Thanks Nigel. Three years ago, I looked at several alternatives for use when sorting small lists. The optimized bubble sort is a good alternative, and a basic qsort might be considered where regular and optimized bubble sorts are too slow. And, of course, the sort shell command is hard to beat where speed and brevity are important. All of these alternatives are intended for use in a script and not a script library.
I just had your ASObjC solution to the stats of the algorithms presented here. The cutoff for switching is somewhere between 10 and 100 items on my old hardware:
QuickSortImprovedStats-v2.pdf (51.6 KB).
I noted that ASObjC sorting on an almost sorted list (only 2 items swapped) is about the same as sorting a random created one.
Like pinpointed by many including Nigel, for sorting different type of lists, pure AppleScript has a use case. Here is the Improved Basic QuickSort modified with Nigel’s comparative script object. I use it a lot with lists of records:
use AppleScript version "2.4" -- Yosemite (10.10) or later
use scripting additions
on QuickSort(ThisList, LeftEnd, RightEnd, CompObect)
-- Will sort items in place from LeftEnd trough RightEnd of TheList using a CompObject script
-- A basic recursive Quicksort, no logical optimisation
-- Based on S.A.R. (Tony) Hoare original algorithm, circa 1959
-- Dichotomic partionionning and code adapted from Niklaus Wirth Pascal version
-- A script object contains the list to allow much faster access to its items
script TonyHoare
property liste : ThisList
on QuickerSort(LeftEnd, RightEnd)
set pivot to my liste's item ((LeftEnd + RightEnd) div 2)
set i to LeftEnd
set j to RightEnd
repeat until i > j
set LeftValue to my liste's item i
repeat while CompObect's IsLarger(pivot, LeftValue)
set i to i + 1
set LeftValue to my liste's item i
end repeat
set RightValue to my liste's item j
repeat while CompObect's IsLarger(RightValue, pivot)
set j to j - 1
set RightValue to my liste's item j
end repeat
if j > i then --> swap items in the list
set my liste's item i to RightValue
set my liste's item j to LeftValue
else if i > j then
exit repeat
end if
set i to i + 1
set j to j - 1
end repeat
if j > LeftEnd then QuickerSort(LeftEnd, j)
if i < RightEnd then QuickerSort(i, RightEnd)
end QuickerSort
end script
TonyHoare's QuickerSort(LeftEnd, RightEnd)
end QuickSort
(* Exemples of CompObject script
script Ascending --> for a simple list, ascending order of sort
on IsLarger(x, y)
x > y
end IsLarger
end script
script Descending --> for a simple list, descending order of sort
on IsLarger(x, y)
x < y
end IsLarger
end script
*)
script ByAgeUp_FirstNameDown
on IsLarger(x, y)
set AgeOfX to x's Age
set AgeOfY to y's Age
(AgeOfX > AgeOfY) or ((AgeOfX = AgeOfY) and (x's FirtName < y's FirtName))
end IsLarger
end script
set MyList to {}
repeat 25 times
set the end of MyList to {FirtName:some character in "BCDFGHJKLMNPRSTVWXZ" & some character in "aeiouy" & ¬
some character in "bcdfgklmnprstxz", Age:random number from 1 to 100}
end repeat
QuickSort(MyList, 1, MyList's length, ByAgeUp_FirstNameDown)
--> {{FirtName:"Faf", Age:1}, {FirtName:"Zad", Age:2}, {FirtName:"Zuc", Age:3}, {FirtName:"Gap", Age:5}, {FirtName:"Bip", Age:5}, {FirtName:"Ryb", Age:15}, {FirtName:"Lyk", Age:15}, {FirtName:"Wud", Age:16}, {FirtName:"Rib", Age:21}, {FirtName:"Set", Age:22}, {FirtName:"Pop", Age:22}, {FirtName:"Gal", Age:23}, {FirtName:"Nud", Age:41}, {FirtName:"Xap", Age:46}, {FirtName:"Wig", Age:56}, {FirtName:"Cab", Age:56}, {FirtName:"Hud", Age:57}, {FirtName:"Vuk", Age:64}, {FirtName:"Pig", Age:64}, {FirtName:"Nod", Age:67}, {FirtName:"Sab", Age:80}, {FirtName:"Lum", Age:88}, {FirtName:"Vom", Age:89}, {FirtName:"Noz", Age:99}, {FirtName:"Det", Age:99}}