Of Scripts and Script Libraries and Sorting Algorithms

Scripting Forums Code Exchange
#1

Over the years Nigel Garvey and others have published some scripts with very fast and sophisticated sorting algorithms.
Over the last few years I’ve had several tries at incorporating his 2010 combined QuickSort+InsertionSort script into my other works but have previously had to give it up due strange behaviour and lack of debugging time.
Now that I am retired and have more time and focus, I have identified the issue.

In 2015 I started using a script library which I implemented as follows:

use U : script “Utilities_1501.scpt”

The script that I copied from Nigel Garvey has a “qsort()” handler (of course), within that handler there is a Script “o”, and within that script several handlers that use the variable “u” and assign various things to it.

 on qsort(theList, l, r) 	script o
 		property cutoff : 10 -- The Quicksort will ignore ranges containing this number of items or fewer.
 		property lst : theList
 		
		on qsrt(l, r) -- The Quicksort handler.
 			set pivot to my lst's item ((l + r) div 2)
 			
 			set i to l
 			set j to r
 			repeat until (i > j)
 				set u to my lst's item i   
-----               ^ here is the problem

Once qsort() has run, the handlers in the Utilities Library script aren’t accessible any more, and for example executing U’s GetTick_Now() results in the bizarre error message:
“5298 doesn’t understand GetTick_Now()”

On careful reading, it seems that this use of use statement creates a property

The fix is simple, a “local U” statement at the beginning of qsort() - I took it two steps further.

 on qsort(theList, l, r)
 	local M, C, G, l, P, U -- hide my Script Library Designators from qsort()
 	local cutoff, lst -- hide script o's properties from outside
	
	script o
 		property cutoff : 10 -- The Quicksort will ignore ranges containing this number of items or fewer.
 		property lst : theList
 		
		on qsrt(l, r) -- The Quicksort handler.
 			local pivot, i, j, u, w --protect the local variables
 			set pivot to my lst's item ((l + r) div 2)
1 Like
#2

I probably should have all of the documentation. If I had followed Nigel’s advice below the problem would have never occured.

– Say you’ve decided to use qsort and it’s in a folder called “Sorts” in your user “Scripts” folder.

set sorter to (load script file ((path to scripts folder as text) & "Sorts:qsort.scpt"))
tell sorter to sort(myList, 1, -1) -- ie. sort items 1 thru -1 of myList.
1 Like
#3

Hi @Ericnepean.

Thanks for your interest in Arthur’s and my Quicksort. I’m glad you were able to work out the cures for the problem you were having by yourself. Nowadays, of course, it’s possible to load the script with the “Libraries” system and a use command in the same way as you load your “Utilities_1501.scpt”, but I still use load script myself occasionally. By the way, the “.scpt” suffix can be omitted from the script name in a use line.

The link to ScriptBuilders in the 2010 addendum to my 2006 post is, as you may already have discovered, no longer valid. ScriptBuilders was a sister site to MacScripter where one could upload actual working files instead of just posting source code as here in Code Exchange. But literally two weeks after I uploaded my sort scripts to it, MacScripter’s then owner discontinued it and the scripts ended up (without my foreknowledge or permission) on some third-party software download site — of which I’ve long since lost track!

#4

Hi Nigel
I belive that after Scriptbuilder went offline, you did update your Macscripters Quicksort post; I got that and I was also lucky enough to download and keep your “Dose of Sorts” compendium before it vanished.

Regarding the third-party software site with your stuff from ScriptBuilders, even Google can’t find that site, which I think is the modern day version of oblivion. :smiley: Serves them right.

1 Like
#5

Is your qsort routine recursive. If so it will run into a recursion limit at around 510, so it would have problems with large lists.
I have a version that doesn’t use recursion and can handle lists of any size.

#6

Hi Robert.

The version referred to above is indeed recursive, but leaves out the deepest few recursion levels, finishing off instead with an insertion sort of the entire sort range. An alternative, which may be slightly faster, is to do individual insertion sorts of the ranges for which recursion isn’t performed. Another alternative is to use recursion only on one of the two partitions at each level (preferably the shorter) and simply to repeat with changed range values for the other.

Quicksort’s recursion doesn’t go straight down, of course. It’s a “divide and conquer” algorithm, so recursion only covers part of the sort range at any one time. There’s a lot of to-ing and fro-ing between levels, but the depth of the deepest level isn’t necessarily as great as one might suppose. I’ve tested all my sorts with lists containing many thousands of items and none of the fully recursive ones have ever hit a recursion limit. The main sticking point has been generating such huge lists in the first place!

But please post your version here in Code Exchange if you think it’s any good. I’d be interested to see it if it’s both in-place and a fully iterative Quicksort as I was never able to produce such a thing myself! :slightly_smiling_face:

#8

Here it is…

on quickSort for blist -- Non-Recursive FASTEST
	local px, stack, lo, hi, L, H, sw -- px means 'Pivot Index'
	script mL
		property alist : blist
		property stack : {{1, count blist}}
	end script
	repeat until (count mL's stack) = 0
		set lo to item 1 of item 1 of mL's stack
		set hi to item 2 of item 1 of mL's stack
		set px to item ((hi + lo) div 2) of mL's alist -- start partitionHoare
		set L to lo
		set H to hi
		repeat
			repeat while item L of mL's alist < px
				set L to L + 1
			end repeat
			repeat while item H of mL's alist > px
				set H to H - 1
			end repeat
			if L ≥ H then exit repeat
			set sw to item L of mL's alist
			set item L of mL's alist to item H of mL's alist
			set item H of mL's alist to sw
			set L to L + 1
			set H to H - 1
		end repeat
		set px to H -- end of partitionHoare
		set mL's stack to rest of mL's stack --items 2 thru -1 of stack
		if px + 1 < hi then set beginning of mL's stack to {px + 1, hi}
		if lo < px then set beginning of mL's stack to {lo, px}
	end repeat
end quickSort
#9

Hi @Fredrik71.

For speed maybe, yes. The main reasons for using an AppleScript sort nowadays would be:

  1. You need an in-place sort.
  2. You need a customised sort that can’t be done with ASObjC.
  3. You just find the algorithm fascinating. :nerd_face: :wink:
1 Like
#10

Hi @robertfern.

Yes. That’s certainly an in-place iterative Quicksort! :sunglasses: — although it’s arguably recursive by proxy, since it implements its own LIFO stack to store range indices instead of using the program stack. :wink: It’s not as fast as the Quicksort to which Ericnepean linked above, probably because of the building and breaking up of the stack and the fact it doesn’t have the insertion sort optimisation. But since your purpose is mainly to avoid any possible recursion limit, that’s probably not important to you.

1 Like
#11

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)

#15

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! :wink:

(*
	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
#16

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.

#17

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.

#18

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

*)
#19

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
*)
#20

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
#21

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
#22

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 :blush: 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! :flushed:

#23

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
--*)
#24

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)