●N×logNとなるソートのハンドラ-2
（マージソート）
N×logNとなるソートの速度を知ろうと思い、マージソートを作ることにしました。これが意外に速く、どこか間違っているんじゃないかとちょっと心配です。
以下がこのスクリプトで5桁の数値のソートに要した時間です。
1000要素 0.5〜0.6秒
5000要素 3〜4秒
10000要素 7〜8秒
20000要素 16秒前後
global stackList, stackListRef, compRecRef, theSortList, theSortListRef
set {stackList, theSortList} to {{}, {}}
set {stackListRef, theSortListRef} to {a reference to stackList, a reference to theSortList}
set compRec to {listA:{}, listB:{}, compList:{}}
set compRecRef to a reference to compRec
set n to {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
set numList to {}
set numListRef to a reference to numList
repeat 1000 times
set end of numListRef to (some item of n) * 10000 + (some item of n) * 1000 + (some item of n) * 100 + (some item of n) * 10 + (some item of n)
end repeat
--set T to current date
--repeat 1 times --速度を計測するために何回か繰り返す
mergeSort(numListRef)
--end repeat
--(current date) - T
on mergeSort(theList)
set i to 2
set n to 2
set countTheList to count theList
set stackList to {}
repeat until i > countTheList
set end of stackListRef to mergeList({item (i - 1) of theList}, {item i of theList})
set i to i + 2
end repeat
if countTheList mod 2 > 0 then set end of stackListRef to {item -1 of theList}
repeat while n < countTheList
set i to 2
set theSortList to {}
repeat until i > (count stackListRef)
set end of theSortListRef to mergeList(item (i - 1) of stackListRef, item i of stackListRef)
set i to i + 2
end repeat
if (count stackListRef) mod 2 > 0 then set end of theSortListRef to item -1 of stackListRef
set n to n * 2
set stackList to theSortList
end repeat
return item 1 of stackListRef
end mergeSort
--以下がソート済みのデータを合体させるルーチン
on mergeList(list_1, list_2)
set compList of compRecRef to {}
if list_1 is {} then return list_2
if list_2 is {} then return list_1
set {listA of compRecRef, listB of compRecRef} to {list_1, list_2}
set {numA, numB} to {1, 1}
set {A, B} to {item 1 of listA of compRecRef, item 1 of listB of compRecRef}
repeat
if A > B then
set {end of compList of compRecRef, numB} to {B, numB + 1}
if numB > (count listB of compRecRef) then exit repeat
set B to item numB of listB of compRecRef
else
set {end of compList of compRecRef, numA} to {A, numA + 1}
if numA > (count listA of compRecRef) then exit repeat
set A to item numA of listA of compRecRef
end if
end repeat
if numA > (count listA of compRecRef) then
repeat until (count listB of compRecRef) < numB
set end of compList of compRecRef to item numB of listB of compRecRef
set numB to numB + 1
end repeat
else
repeat until (count listA of compRecRef) < numA
set end of compList of compRecRef to item numA of listA of compRecRef
set numA to numA + 1
end repeat
end if
return compList of compRecRef
end mergeList
