You are correct, SIR! ( to be read in the voice of Ed McMahon)
I also have a version that will sort a list of lists where you send it a sort list parameter that contains the item indexes to sort on and also add a minus sign to the ones you want sorted in reverse order. (I.e. descending)
I’ve been fooling with the iterative Quicksort @robertfern posted for the past couple of days, having just rediscovered it on my desktop where it’s been since November.
I’ve reworked it in my own “style” (for want of a better word) and have speeded it up a bit with insertion sorting for short partitions and a further reduction of stack work by simply resetting a range variable where possible instead of pushing a list onto the stack and immediately pulling it off again. I did think of adding median-of-3 pivot selection as well, but the code’s long and spindly enough as it is! 
(*
Iterative (ie. non-recursive) in-place Quicksort with insertion sorting of short partitions.
Quicksort algorithm: Tony Hoare
Insertion sort idea: probably Robert Sedgewick
*)
-- Sort items l thru r of theList in place.
on quicksort(theList, l, r)
-- Check input.
set listLen to (count theList)
-- Negative and/or transposed range indices.
if (l < 0) then set l to listLen + l + 1
if (r < 0) then set r to listLen + r + 1
if (l > r) then set {l, r} to {r, l}
if ((l < 1) or (r > listLen)) then error "Quicksort: range parameter(s) out of — er — range."
if (listLen < 2) then return
script o -- Contains the list and the stack for speed and the insertion sort handler for convenience.
property lst : theList
property stack : {{l, r}}
on isrt(l, r) -- Insertion sort.
-- Set up a minor optimisation whereby the most recent instance of any value that's the highest so far
-- in the insertion sort is only put back into the list when superseded or to complete the sort.
set highestSoFar to my lst's item l
set v to my lst's item (l + 1)
if (highestSoFar > v) then
set my lst's item l to v
else
set highestSoFar to v
end if
repeat with i from (l + 2) to r
set v to my lst's item i
if (highestSoFar > v) then
repeat with j from (i - 2) to l by -1
tell my lst's item j
if (it > v) then
set my lst's item (j + 1) to it
else
set j to j + 1
exit repeat
end if
end tell
end repeat
set my lst's item j to v
else
set my lst's item (i - 1) to highestSoFar
set highestSoFar to v
end if
end repeat
set my lst's item r to highestSoFar
end isrt
end script
set cutoff to 10 -- Partitions with this or fewer items are insertion sorted.
set getFromStack to true -- Whether or not to pull a pair of range indices from the stack.
repeat
if (getFromStack) then
if ((count o's stack) = 0) then exit repeat -- Finished when stack exhausted.
set {l, r} to o's stack's beginning
set o's stack to o's stack's rest
else
set getFromStack to true
end if
set pivot to o's lst's item ((l + r) div 2)
set i to l
set j to r
-- Partition the current range into values ≤ 'pivot' and values ≥ 'pivot'.
repeat while (j > i)
set iv to o's lst's item i
repeat while (iv < pivot)
set i to i + 1
set iv to o's lst's item i
end repeat
set jv to o's lst's item j
repeat while (jv > pivot)
set j to j - 1
set jv to o's lst's item j
end repeat
if (i > j) then
else
set o's lst's item i to jv
set o's lst's item j to iv
set i to i + 1
set j to j - 1
end if
end repeat
-- Decide how to handle the partitions.
if (r - i < cutoff) then -- 'cutoff' or fewer items in the hi partition.
-- If more than 1 item, insertion sort the partition. Otherwise leave it.
if (r > i) then o's isrt(i, r)
if (j - l < cutoff) then
-- Likewise with the lo partition if it has 'cutoff' or fewer items.
if (j > l) then o's isrt(l, j)
else
-- Otherwise reset the right index variable ready to subpartition the lo partition next time round the repeat.
set r to j
set getFromStack to false
end if
else -- *More* than 'cutoff' items in the hi partition.
if (j - l < cutoff) then -- 'cutoff' or fewer items in the lo partition.
-- Insertion sort or leave the lo partition .
if (j > l) then o's isrt(l, j)
-- Reset the left index variable to subpartition the hi partition in the next iteration.
set l to i
else -- More than 'cutoff' items in the lo partition.
-- Stack the hi partition's range indices.
set o's stack's beginning to {i, r}
-- Reset the right index variable to subpartition the lo partition in the next iterationt.
set r to j
end if
set getFromStack to false
end if
end repeat
return -- nothing.
end quicksort
-- Demo:
set lst to {}
repeat 100 times
set my lst's end to (random number 500)
end repeat
-- Sort items 1 thru -1 of lst in place.
quicksort(lst, 1, -1)
return lst
If anyone’s interested, one way to include median-of-3 pivot selection is to replace these four lines:
set pivot to o's lst's item ((l + r) div 2)
set i to l
set j to r
-- Partition the current range into values ≤ 'pivot' and values ≥ 'pivot'.
… with this:
(* MEDIAN-OF-3 PIVOT SELECTION *)
-- Reduce the chances of picking this range's lowest or highest value as the
-- pivot value by using the median of the range's first, middle, and last values.
-- Combine finding this with ordering the values in those slots so that
-- they won't need to be tested again in the partitioning repeat.
set m to (l + r) div 2
set pivot to o's lst's item m -- The default unless changed below.
set lv to o's lst's item l
set rv to o's lst's item r
if (lv > rv) then
if (pivot > lv) then -- (pivot > lv > rv)
set o's lst's item l to rv
set o's lst's item m to lv
set o's lst's item r to pivot
set pivot to lv
else if (rv > pivot) then -- (lv > rv > pivot)
set o's lst's item l to pivot
set o's lst's item m to rv
set o's lst's item r to lv
set pivot to rv
else
set o's lst's item l to rv
set o's lst's item r to lv
end if
else if (pivot > rv) then -- (pivot > rv ≥ lv)
set o's lst's item m to rv
set o's lst's item r to pivot
set pivot to rv
else if (lv > pivot) then -- (rv ≥ lv > pivot)
set o's lst's item l to pivot
set o's lst's item m to lv
set pivot to lv
end if
(* END *)
-- Partition the range into values ≤ 'pivot' and values ≥ 'pivot'. (End values already done.)
set i to l + 1
set j to r - 1
The speed improvement’s only marginal and is statistical rather than assured in any particular case.
Hi Nigel, thanks for the update. I do use your algorithms (especially the ones that implement parallel sorting) in improving the speed of some of my applications for CaptureOne.
I use this plain recursive Quicksort routine all the time. Faster than Robert Fern’s iterative solution. It works easily with a 10, 000 items list on a Mid-2013 MacBook Air with 4GB of ram. AppleScript manages stacks for recursion very well I believe.
use AppleScript version "2.4" -- Yosemite (10.10) or later
use scripting additions
on QuickSort(ThisList, LeftEnd, RightEnd)
-- Will sort items in place from LeftEnd trough RightEnd of TheList
-- 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 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 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
(* Example
script GetTick
use framework "Foundation" --> for more precise timing calculations
on Now()
return (current application's NSDate's timeIntervalSinceReferenceDate) as real
end Now
end script
set MyList to {}
repeat 10000 times
set the end of MyList to random number from 1 to 10000
end repeat
set t1 to GetTick's Now()
QuickSort(MyList, 1, MyList's length)
(GetTick's Now()) - t1
*)
With a 10, 000 items list, I get 3 times faster sorting than my previous version of plain Quicksort I had picked up somewhere on macscripter. I am not sure where the gain is from. Maybe Nigel has a clue.
on QuickSort(ThisList, LeftEnd, RightEnd)
--> Sorts list in place
script QS --> list in script object speeds up access to it's element
property Array : ThisList
end script
set i to LeftEnd
set j to RightEnd
set pivot to QS's Array's item ((LeftEnd + RightEnd) div 2)
repeat while j > i
repeat while QS's Array's item i < pivot
set i to i + 1
end repeat
repeat while QS's Array's item j > pivot
set j to j - 1
end repeat
if not (i > j) then --> let's swap item in the list
tell (a reference to QS's Array)
set TempValue to item i
set item i to item j
set item j to TempValue
end tell
set i to i + 1
set j to j - 1
end if
end repeat
if LeftEnd < j then QuickSort(QS's Array, LeftEnd, j)
if RightEnd > i then QuickSort(QS's Array, i, RightEnd)
end QuickSort
(*
--Exemple
set MyList to {}
repeat 10000 times
set the end of MyList to random number from 1 to 10000
end repeat
set t1 to GetTick's Now()
QuickSort(MyList, 1, MyList's length)
(GetTick's Now()) - t1
script GetTick --> for more precise timing calculations
use framework "Foundation"
on Now()
return (current application's NSDate's timeIntervalSinceReferenceDate) as real
end Now
end script
*)
I updated this to use middle-of-three, bubble sort when the items are 3 or less, and to use a stack rather than recursion. The major difference is that there is a no longer a stack overflow with a mostly-sorted list.
on QuickSort(ThisList)
local LeftEnd, RightEnd, pivot, a, b, c, i, j, TempValue, diff, WasChanged
set LeftEnd to 1
set RightEnd to length of ThisList
--> Sorts list in place
script QS --> list in script object speeds up access to it's element
property Array : ThisList
property stack : {{LeftEnd, RightEnd}}
end script
set stackIndex to 1
set stackLength to 1
repeat while stackIndex > 0
set {LeftEnd, RightEnd} to item stackIndex of QS's stack
set stackIndex to stackIndex - 1
set diff to RightEnd - LeftEnd + 1
if diff ≤ 1 then
-- Do nothing
else if diff = 2 then
set a to item LeftEnd of QS's Array
set b to item RightEnd of QS's Array
if a > b then
set item LeftEnd of QS's Array to b
set item RightEnd of QS's Array to a
end if
else if diff = 3 then
set a to item LeftEnd of QS's Array
set b to item (LeftEnd + 1) of QS's Array
set c to item RightEnd of QS's Array
set WasChanged to false
if a > c then
set TempValue to a
set a to c
set c to TempValue
set WasChanged to true
end if
if a > b then
set TempValue to a
set a to b
set b to TempValue
set WasChanged to true
end if
if b > c then
set TempValue to b
set b to c
set c to TempValue
set WasChanged to true
end if
if WasChanged then
set item LeftEnd of QS's Array to a
set item (LeftEnd + 1) of QS's Array to b
set item RightEnd of QS's Array to c
end if
else
set i to LeftEnd
set j to RightEnd
set MidPoint to (LeftEnd + RightEnd) div 2
set a to item LeftEnd of QS's Array
set b to item MidPoint of QS's Array
set c to item RightEnd of QS's Array
if (a ≤ b and b ≤ c) or (a ≥ b and b ≥ c) then
set pivot to b
else if (a ≤ c and c ≤ b) or (a ≥ c and c ≥ b) then
set pivot to c
else
set pivot to a
end if
repeat while j > i
repeat while QS's Array's item i < pivot
set i to i + 1
end repeat
repeat while QS's Array's item j > pivot
set j to j - 1
end repeat
if not (i > j) then --> let's swap item in the list
tell (a reference to QS's Array)
set TempValue to item i
set item i to item j
set item j to TempValue
end tell
set i to i + 1
set j to j - 1
end if
end repeat
if LeftEnd < j then
set stackIndex to stackIndex + 1
set item stackIndex of QS's stack to {LeftEnd, j}
end if
if RightEnd > i then
set stackIndex to stackIndex + 1
if stackIndex > stackLength then
set end of QS's stack to {i, RightEnd}
set stackLength to stackLength + 1
else
set item stackIndex of QS's stack to {i, RightEnd}
end if
end if
end if
end repeat
end QuickSort
I find sorting algorithms fascinating, so I wrote a MergeSort that is slightly faster than that QuickSort, and significantly faster when the list is already mostly sorted.
on MergeSort(someList)
local listLen, lastIndex, i
script MS
property originalList : someList
property currentList : {}
property newList : {}
end script
set listLen to length of someList
repeat with i from 1 to listLen
set end of MS's currentList to {item i of MS's originalList}
end repeat
repeat while listLen > 1
set lastIndex to listLen - 1
repeat with listIndex from 1 to lastIndex by 2
set end of MS's newList to MergeThese(item listIndex of MS's currentList, item (listIndex + 1) of MS's currentList)
end repeat
if listLen mod 2 = 1 then
set end of MS's newList to item -1 of MS's currentList
set listLen to (listLen div 2) + 1
else
set listLen to listLen div 2
end if
set MS's currentList to MS's newList
set MS's newList to {}
end repeat
item 1 of MS's currentList
end MergeSort
on MergeThese(list1, list2)
local a, b, i, l1Index, l1Length, l2Index, l2Length
script MT
property l1 : list1
property l2 : list2
property newList : {}
end script
set l1Length to length of MT's l1
set l2Length to length of MT's l2
set l1Index to 1
set l2Index to 1
repeat
if l1Index > l1Length then
repeat with i from l2Index to l2Length
set end of MT's newList to item i of MT's l2
end repeat
exit repeat
else if l2Index > l2Length then
repeat with i from l1Index to l1Length
set end of MT's newList to item i of MT's l1
end repeat
exit repeat
else
set a to item l1Index of MT's l1
set b to item l2Index of MT's l2
if a > b then
set end of MT's newList to b
set l2Index to l2Index + 1
else
set end of MT's newList to a
set l1Index to l1Index + 1
end if
end if
end repeat
MT's newList
end MergeThese
My magnum opus is a customisable iterative ternary merge sort that’s pretty fast by AppleScript standards but largely rendered obsolete by the Foundation sort accessible through ASObjC. I still use it — partly because I wrote it 
and partly because it can do one or two things the ASObjC one still can’t. I’ll have to look at it again some day to see if I can still understand it! 
It’s been a rainy day here, so here’s a recursive Quicksort with median-of-3 pivot selection, insertion sorting of short partitions, and tail call elimination.
(* Quicksort with median-of-3 pivot selection, insertion sorting of short partitions, and tail call elimination.
Quicksort algorithm: S.A.R. (Tony) Hoare, 1960.
Optimisation ideas by Robert Sedgewick (1975?).
AppleScript Quicksort implementation: Arthur J. Knapp and Nigel Garvey, 2003.
Sedgwick implementations by Nigel Garvey, 2010, 2018, 2025, & 2026.
Parameters: (list, range index 1, range index 2)
As with AppleScript's range specifiers, the range indices can be passed as positives or negatives and in either order.
*)
on Quicksort(theList, rangeIndex1, rangeIndex2)
script o
property cutoff : 10 -- Insertion sorting replaces recursion with partitions ≤ this length.
property lst : theList
on qsrt(l, r) -- Quicksort handler.
repeat -- Tail call elimination repeat.
(* MEDIAN-OF-3 PIVOT SELECTION COMBINED WITH ORDERING OF THE 3 CANDIDATES. *)
set m to (l + r) div 2
set pivot to my lst's item m
set lv to my lst's item l
set rv to my lst's item r
if (lv > rv) then
if (pivot > lv) then -- (pivot > lv > rv)
set o's lst's item l to rv
set o's lst's item m to lv
set o's lst's item r to pivot
set pivot to lv
else if (rv > pivot) then -- (lv > rv > pivot)
set o's lst's item l to pivot
set o's lst's item m to rv
set o's lst's item r to lv
set pivot to rv
else
set o's lst's item l to rv
set o's lst's item r to lv
end if
else if (pivot > rv) then -- (pivot > rv ≥ lv)
set o's lst's item m to rv
set o's lst's item r to pivot
set pivot to rv
else if (lv > pivot) then -- (rv ≥ lv > pivot)
set o's lst's item l to pivot
set o's lst's item m to lv
set pivot to lv
end if
(* PARTITIONING OF REMAINING VALUES. *)
set i to l + 1
set j to r - 1
repeat until (i > j)
set iv to my lst's item i
repeat while (iv < pivot)
set i to i + 1
set iv to my lst's item i
end repeat
set jv to my lst's item j
repeat while (jv > pivot)
set j to j - 1
set jv to my lst's item j
end repeat
if (j > i) then
set my lst's item i to jv
set my lst's item j to iv
else if (i > j) then
exit repeat
end if
set i to i + 1
set j to j - 1
end repeat
(* RECURSION, INSERTION SORT, OR TAIL CALL ELIMINATION. *)
-- Insertion sort or recursion for the shorter partition, then insertion sort or repeat for the longer.
set leftDiff to j - l
set rightDiff to r - i
if (leftDiff > rightDiff) then
if (rightDiff < cutoff) then
isrt(i, r)
else
qsrt(i, r)
end if
if (leftDiff < cutoff) then
isrt(l, j)
exit repeat
else
set r to j
end if
else
if (leftDiff < cutoff) then
isrt(l, j)
else
qsrt(l, j)
end if
if (rightDiff < cutoff) then
isrt(i, r)
exit repeat
else
set l to i
end if
end if
end repeat -- End tail call elimination repeat.
end qsrt
on isrt(l, r) -- Insertion sort handler.
set highestV to my lst's item l -- Latest instance of highest value so far.
set currentV to my lst's item (l + 1) -- Value currently to be placed.
if (highestV > currentV) then
set my lst's item l to currentV
else
set highestV to currentV
end if
repeat with j from (l + 2) to r
set currentV to my lst's item j
if (highestV > currentV) then
repeat with i from (j - 2) to l by -1
tell my lst's item i
if (it > currentV) then
set my lst's item (i + 1) to it
else
set i to i + 1
exit repeat
end if
end tell
end repeat
set my lst's item i to currentV
else
set my lst's item (j - 1) to highestV
set highestV to currentV
end if
end repeat
set my lst's item r to highestV
end isrt
end script
-- (* PROCESSING OF INPUT PARAMETERS. *)
set listLen to (count theList)
if (listLen > 1) then
-- Negative and/or transposed range indices.
if (rangeIndex1 < 0) then set rangeIndex1 to listLen + rangeIndex1 + 1
if (rangeIndex2 < 0) then set rangeIndex2 to listLen + rangeIndex2 + 1
if (rangeIndex1 > rangeIndex2) then set {rangeIndex1, rangeIndex2} to {rangeIndex2, rangeIndex1}
-- Do the sort.
if (rangeIndex2 - rangeIndex1 < o's cutoff) then
o's isrt(rangeIndex1, rangeIndex2)
else
o's qsrt(rangeIndex1, rangeIndex2)
end if
end if
return -- nothing.
end Quicksort
property sort : Quicksort
--(* Demo:
set l to {}
repeat with i from 1 to 1000
set end of my l to (random number 10000)
end repeat
sort(l, 1, -1)
l
--*)
I did a speed comparison of the algorithms presented.
I build 5 reference lists:
use AppleScript version "2.4" -- Yosemite (10.10) or later
use scripting additions
repeat with i from 1 to 5
set n to (10 ^ i) as integer
set MyList to {}
repeat n times
set the end of MyList to random number from 1 to n
end repeat
set OutFile to open for access (choose file name) with write permission
write MyList to OutFile as list
close access OutFile
end repeat
I then compared 6 sort algorithms with the reference lists. Not only that, but I also timed a list where I swapped the 2nd item with 2nd last item to test them with an almost sorted list. Something like this for sorts that that work in place, but a little different for those that creates a new sorted list.
script GetTick --> for more precise timing calculations
use framework "Foundation"
on Now()
return (current application's NSDate's timeIntervalSinceReferenceDate) as real
end Now
end script
set InFile to open for access (choose file)
set MyList to read InFile as list
close access InFile
set t1 to GetTick's Now()
QuickSort(MyList, 1, MyList's length)
set t2 to GetTick's Now()
tell MyList
set TempValue to 2nd item
set 2nd item to item -2
set item -2 to TempValue
end tell
set t3 to GetTick's Now()
QuickSort(MyList, 1, MyList's length)
set t4 to GetTick's Now()
set Timings to {t2 - t1, t4 - t3}
Results are in enclosed PDF. Nigel’s Optimized QuickSort is winning everywhere. The improved basic QuickSort is 2nd in all tests and a big improvement over the basic version, which was my reason for posting it. No issues such as stack overflows with it up to 100, 000 items or with an almost sorted list.
QuickSortStast.pdf (48.3 KB)
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}}