Having enjoyed Kevin Bradley’s ScriptWire article on sorting methods last month, I though I’d have a go at writing a merge sort, and finally got around to it this weekend. Like the qsort handler that Arthur Knapp and I wrote a few years ago, the effort below sorts “in place” “ that is, it sorts the actual list it’s fed. It doesn’t return a sorted copy. It can also sort just part of a list, if required. It’s not quite as fast as qsort, but it’s not bad.

Merge sort is a recursive, divide-and-conquer algorithm that sorts each half of a list and then “merges” the two halves into a sorted whole. Before that, the halves of the halves are sorted, and so on. At the deepest level of recursion, the “halves” are already ordered internally by virtue of having less than two items!

The customary implementation seems to be to create a “left list” and a “right list” at each level of recursion and to chop these up into smaller lists while building yet another, “merged” list, which is then passed back upstream for use at the previous level. My effort reduces the amount of list waste by only creating one extra list at each recursion level. This list is a copy of the whole of the current section after the two halves have been sorted. Two pointers are used to index the two halves, which are merged directly back to the part of original list from which the copy was taken.

```
(* Merge sort
Merge sort algorithm: John von Neumann, 1945.
AppleScript implementation: Nigel Garvey, 2007/2015.
Parameters: (list, range index 1, range index 2)
*)
on mergeSort(theList, l, r) -- Sort items l thru r of theList.
script o
property lst : theList
property auxList : missing value
on msrt(l, r)
set leftR to (l + r) div 2 -- Left half end index.
set rx to leftR + 1 -- Right half start/tracking index.
-- Sort the left half by recursion if it has more than two items or by swapping as necessary if there are two. If one, do nothing.
if (leftR - l > 1) then
msrt(l, leftR)
else if (leftR > l) then
set lv to item l of my lst
set rv to item leftR of my lst
if (rv < lv) then
set item l of my lst to rv
set item leftR of my lst to lv
end if
end if
-- Sort the right half similarly.
if (r - rx > 1) then
msrt(rx, r)
else if (r > rx) then
set lv to item rx of my lst
set rv to item r of my lst
if (rv < lv) then
set item rx of my lst to rv
set item r of my lst to lv
end if
end if
-- Extract a separate list of the left half's items and set tracking and end indices for it.
set auxList to items l thru leftR of my lst
set lx to 1
set leftR to rx - l
-- Iterate through the range, merging the two halves by comparing the lowest unassigned value from auxList with that from the right half of the range and assigning the lower of the two (or the left if they're equal) to the current slot.
-- Begin with the first (lowest) value from each half.
set lv to beginning of my auxList
set rv to item rx of my lst
repeat with dx from l to r
if (rv < lv) then
-- The right value's less than the left. Assign it to this slot.
set item dx of my lst to rv
-- If no more right-half values, assign the remaining left values to the remaining slots and exit this repeat and recursion level.
if (rx is r) then
repeat with dx from (dx + 1) to r
set item dx of my lst to item lx of my auxList
set lx to lx + 1
end repeat
exit repeat
end if
-- Otherwise get the next right-half value.
set rx to rx + 1
set rv to item rx of my lst
else
-- The left value's less than or equal to the right.
set item dx of my lst to lv
-- If no more left-half values, simply exit this repeat and recursion level as the remaining right values are in place anyway.
if (lx is leftR) then exit repeat
-- Otherwise get the next left-half value
set lx to lx + 1
set lv to item lx of my auxList
end if
end repeat
end msrt
end script
-- Process the input parameters.
set listLen to (count theList)
if (listLen > 1) then
-- 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}
-- Do the sort.
o's msrt(l, r)
end if
return -- nothing
end mergeSort
property sort : mergeSort
-- (* Demo:
set l to {}
repeat 1000 times
set end of my l to (random number 1000)
end repeat
sort(l, 1, -1)
l
-- *)
```

13th September 2010: I’ve uploaded a new version of this script, as part of a collection, to ScriptBuilders.

29th November 2013: Since ScriptBuilders is now defunct and unlikely to return, I’ve replaced the code originally posted here with the latest version.

14th June 2015: The amount of waste has been further reduced (after eight years!) by only extracting the left halves of the merge ranges to the separate lists. Comments and variable names have been changed and the former mutually recursive sortHalf() handler has been replaced with a couple of bits of in-line code.