Hello.
The handlers below are based on the quicksort algorithm, where we do take advantage of the fact that we don’t need to perform a full sort in order to find the median of a list of numbers. The median is defined to be floor (n+1/ 2) if n is odd, and ceil(n+1/2) if n is even, where n is the length of the list of numbers.
|median| has a best/average case of O(n) , and a worst case performance of O(n^2) (sorted list, or reverse ordered).
There is a better way, to find the median, which works quite differently, the median of medians algorithm, that I may come back to. There is an easy way to get the median by Satimage.osax/smile, so I am not sure if it is worth the bother. 
Edit
New version that works correctly.
New version that more than halves the time used, due to using a “local” random number generator.
New version that halves the time again for 1000 elements, I have changed the partitioning algorithm.
(* Demo
set maxitems to 1000
set L to {}
repeat maxitems times
set end of L to rand(1, maxitems)
end repeat
set max to 0
repeat with i from 1 to maxitems
if item i of L > max then set max to item i of L
end repeat
log "max: " & max
set min to (maxitems + 1)
repeat with i from 1 to maxitems
if item i of L < min then set min to item i of L
end repeat
log "min: " & min
set t0 to (current date)
repeat 1000 times
set {md, k} to |median|(L)
end repeat
set t1 to ((current date) - t0) / 1000
log "time T : " & t1
log "median val: " & md
set m to sortlist L -- Satimage needed!
log "low: " & item (k - 1) of m
log "median: " & item k of m
log "high: " & item (k + 1) of m
*)
script pseudo
-- pure multiplicative random generator.
-- Its faster most of the time than Standard Additions random number (10000 runs).
-- it has been proved that the sequence doesn't repeat itself before 2^31 -2 calls have been made.
-- yet: No warranties about anything.
-- Rosen "Discrete Mathematics" p. 207
property x0 : 3
property rmod : 2 ^ 31 - 1
property multiplier : 7 ^ 5
on rand()
set x0 to (multiplier * x0) mod rmod
return (x0 / 1.0E+9)
end rand
on init()
rand()
end init
end script
on partition(|L|, low, high, pivotIndex)
-- N. Wirth: Algorithms and Datastructures p. 93
-- Implemented in AppleScript by McUsr
(*
Excerpt:
Let us try the following algorithm:
Pick any item at random (and call it x ):
scan the array from the left until an item a_i > x is found
then scan from the right until an item a_j < x is found.
Now exchange the two items and continue this scan and swap process until
the two scans meet somewhere in the middle of the array.
The result is that the array is now partitioned into a left part with keys
≤ x, and a right part with keys ≥ x.
*)
script o
property L : |L|
end script
-- select an item x at random
set x to item pivotIndex of o's L
set i to low
set j to high
repeat while i ≤ j
repeat while item i of o's L < x
set i to i + 1
end repeat
repeat while x < item j of o's L
set j to j - 1
end repeat
if i < j then
set w to item i of o's L
set item i of o's L to item j of o's L
set item j of o's L to w
end if
if i ≤ j then
set i to i + 1
set j to j - 1
end if
end repeat
return i - 1 -- last element of the "left" partition
end partition
on randSelect(|L|, low, high, k)
script o
property L : |L|
end script
-- selects the k smallest integer (used for the median).
-- It uses the basics of quicksort, to puth the k least integer
-- into the kth position, which is then returned. It does so
-- by partionting the list of elements, and returns the kth element
-- when the list have been partioned on k.
-- Implemented in AppleScript by McUsr: Standard quick select as fouund on:
-- http://www.catonmat.net/blog/mit-introduction-to-algorithms-part-four/
if low = high then return item low of o's L
set r to high - low + 1
-- set r to ((random number) * r mod r div 1 + low)
set r to ((pseudo's rand()) * r mod r div 1 + low)
set r to partition(o's L, low, high, r)
set n to r - low + 1
if k = n then
return item r of o's L
else if k < n then
return randSelect(o's L, low, r - 1, k)
else
randSelect(o's L, r + 1, high, k - n)
end if
end randSelect
on |median|(L)
-- returns the median in a list of numbers
-- it alters L, save a copy before invoking this
-- handler, if you need the original list.
-- Thanks to Nigel Garvey for spotting the problems
-- with the first version.
set ll to length of L
if ll mod 2 = 0 then
set k to ll div 2
else
set k to (ll + 1) div 2
end if
pseudo's init()
return {randSelect(L, 1, ll, k), k}
end |median|
on rand(low, high)
-- returns a random integer, within low and high inclusive
-- Made by McUsr
set k to high - low + 1
return ((random number) * k mod k div 1 + low)
end rand
I use three handlers, nor am I going to optimize it, as there is a better algorithm out there that is probably easier to implement (median of medians), should I ever need something faster than yours.