Here’s the CustomQsort handler I mentioned earlier. Sorts work by comparing items in a list and repositioning them according to their relative values. But comparing items directly isn’t always possible or desirable. You might want to sort a list of lists, or of records, or of files, or even of mixed classes. Or the sort order might need to be modified in some way. Each contingency requires a different method for determining which items are “greater” or “less” than others, which means having either several specialised sort handlers or a customisable one such as CustomQsort. CustomQsort does the physical work of moving items around in the list, but the comparisons are done by short handlers in a script object that’s passed to CustomQsort as a parameter.
Arthur and I had slightly different preferences for what the script object should contain, so this is just my version:
13th September 2010: I’ve uploaded a new version of this sort with an improved customisation regime, as part of a collection, to ScriptBuilders. The new version, though, will accept customisation scripts written for the one below, which has been around for quite a while now.
on CustomQsort(theList, l, r, compObj)
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 (compObj's isLess(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 (compObj's isGreater(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
-- Inform the script object of this swap.
compObj's swap(i, j)
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 (compObj's isLess(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
-- Inform the script object of this swap.
compObj's swap(l, x)
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 (compObj's isLess(v, u)) then
set my p's item i to u
repeat with j from (i - 2) to l by -1
if (compObj's isLess(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
-- Inform the script object of this insertion.
compObj's shift(j + 1, i)
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 CustomQsort
The compObj parameter should be a script object containing these four handlers and anything else that may be required:
isLess(a, b): decides if the value of a is “less” than the value of b or not. (Returns ‘true’ or ‘false’.)
isGreater(a, b): decides if the value of a is “greater” than the value of b, ditto.
swap(a, b): called by CustomQsort after each swap performed in the list being sorted. a and b are the indices of the swapped items. This handler would normally be left empty, but it could be used to do the same swap in another list.
shift(a, b): called by CustomQsort after each “insertion” performed in the list being sorted. The parameters indicate that item b of the list has been moved to position a after items a thru (b - 1) have been shifted uplist. This handler would also normally be left empty, but could be used to echo the moves in another list.
The idea is that you write your own script objects to control how the sort is done. For a straightforward sort similar to qsort’s, isLess() and isGreater() would do simple comparisons and swap() and shift() would do nothing:
script standardSort
on isLess(a, b)
(a < b)
end isLess
on isGreater(a, b)
(a > b)
end isGreater
on swap(a, b)
end swap
on shift(a, b)
end shift
end script
CustomQsort(myList, 1, -1, standardSort)
If you wanted to sort one list and echo the moves in another ” say you had a list of files that had to be sorted in parallel with a list of corresponding modification dates ” you’d use the swap() and shift() handlers to perform the slave moves in the file list:
script slaveSort
property slaveList : missing value
on isLess(a, b)
(a < b)
end isLess
on isGreater(a, b)
(a > b)
end isGreater
-- Do the same swap in slaveList that CustomQsort has just done in the list it's sorting.
on swap(a, b)
tell item a of my slaveList
set item a of my slaveList to item b of my slaveList
set item b of my slaveList to it
end tell
end swap
-- Do the same shift and insertion in slaveList that CustomQsort has just done in the list it's sorting.
on shift(a, b)
tell item b of my slaveList
repeat with i from b - 1 to a by -1
set item (i + 1) of my slaveList to item i of my slaveList
end repeat
set item a of my slaveList to it
end tell
end shift
end script
set slaveSort's slaveList to myFileList
CustomQsort(myDateList, 1, -1, slaveSort)
--> myDateList sorted by the dates it contains
--> myFileList sorted so that the files still correspond to the dates
For a spreadsheet-style sort, sorting a list of lists on, say, the third item in each list:
script listSort
property i : missing value
on isLess(a, b)
(a's item i < b's item i)
end isLess
on isGreater(a, b)
(a's item i > b's item i)
end isGreater
on swap(a, b)
end swap
on shift(a, b)
end shift
end script
set listSort's i to 3
CustomQsort(myListOfLists, 1, -1, listSort)
For a reverse sort, simply lie to CustomQsort by swapping the contents of the isLess() and isGreater() handlers. 
script reverseSort
on isLess(a, b)
(a > b)
end isLess
on isGreater(a, b)
(a < b)
end isGreater
on swap(a, b)
end swap
on shift(a, b)
end shift
end script
CustomQsort(myList, 1, -1, reverseSort)
And so on.
Within the same script, handlers and properties that are common to different script objects can be shared. For example, if there’s a standard sort and a reverse sort in the same script, the amount of code in one of the script objects could be reduced by making it a child of the other:
script standardSort
on isLess(a, b)
(a < b)
end isLess
on isGreater(a, b)
(a > b)
end isGreater
on swap(a, b)
end swap
on shift(a, b)
end shift
end script
script reverseSort
property parent : standardSort
on isLess(a, b)
(a > b)
end isLess
on isGreater(a, b)
(a < b)
end isGreater
end
With standardSort as its ‘parent’, reverseSort inherits all standardSort’s handlers (and would inherit its properties too, if it had any), so there’s no need to write out the swap() and shift() handlers in reverseSort itself. The other two handlers, though, have to be different and so are written out, which overrides the inheritance as far as they’re concerned. The two script objects thus have their own isLess() and isGreater() handlers, but share standardSort’s swap() and shift() handlers.
It’s possible to go even further with the above example, as reverseSort’s isLess() and isGreater() handlers are the same as standardSort’s isGreater() and isLess() handlers. These too can be shared by assigning them to the relevantly named variables in reverseSort. The full specification for the reverseSort script object would then be:
script reverseSort
property parent : standardSort
property isLess : standardSort's isGreater
property isGreater : standardSort's isLess
end script
(an old fart in the sun)