Let’s see if I can be coherent at 2:30 in the morning.
Arthur’s script sorts “in place” - ie. it rearranges the items in the original list. (It doesn’t create a sorted copy.) Because of its form, you have to specify start values for the indices that delimit the sort area in the list. To sort the entire list, the start indices must be the first and last in the list - ie. 1 and the list’s length.
on QuickSort(a, l, r)
(*
* Sorts "in-place":
*
* set a to { 2, 3, 1 }
*
* QuickSort( a, 1, a's length ) -- no return value
*
* get a --> { 1, 2, 3 }
*)
local i, j, v --> SD debugging
(* Much thanks to Serge Belleudy-d'Espinose for that
* extra surge of speed. :-)
*)
script o
property p : a
end script
For arcane technical reasons, access to items in a list is faster if you use a reference to refer to the list rather than a simple variable. By assigning the list to a property ‘p’ in a script object ‘o’, you can call it ‘o’s p’ (a reference) rather than simply ‘a’ (a straightforward variable). Serge Belleudy-d’Espinose is credited with discovering this technique.
set i to l
set j to r
set v to o's p's item ((l + r) div 2)
‘l’ and ‘r’ are the left and right limits of the sort in each particular iteration of the handler. ‘i’ and ‘j’ start off as copies of these and then move towards each other. ‘v’ is the value of an item approximately in the middle of the sort area. The goal for each iteration is that all items to the left of the centre item should less than or equal to it, and all items to the right should be greater than or equal to it.
repeat while (j > i)
Repeat until the converging indices meet or cross.
repeat while (o's p's item i < v)
set i to i + 1
end repeat
Move the left moveable index to the right until an item’s found that’s NOT less than the centre item.
repeat while (o's p's item j > v)
set j to j - 1
end repeat
Similarly, move the right moveable index to the left until an item’s reached that’s not greater than the centre item.
if (not i > j) then
(* set { i, j } to { j, i }
*)
set o_s_p_s_item_i to o's p's item i
set o's p's item i to o's p's item j
set o's p's item j to o_s_p_s_item_i
set i to i + 1
set j to j - 1
end if
end repeat
If the moveable indices haven’t crossed, exchange the item on the left with the item on the right and converge the indices again by one step each. Continue until the indices meet or cross in the middle, by which time all the items to the left will be less than or equal to the centre item and all the items to the right will be greater than or equal to it.
if (l < j) then QuickSort(o's p, l, j)
if (r > i) then QuickSort(o's p, i, r)
return a
end QuickSort
If the moving right index hasn’t reach this iteration’s fixed left index, recursively subsort the items between them. Similarly, if the moving left index hasn’t reached this iteration’s fixed right index, recursively subsort the items between them. Each iteration sorts a different area of the same list. If you specify, say, ‘myList’ as a parameter when you call QuickSort, ‘myList’ will be sorted by the end of the process. The ‘return a’ is thus a complete waste of time and I’d guess it wasn’t in Arthur’s original script.