●N×logNとなるソートのハンドラ-1
（クイックソート---失敗例）
実はこれまで実験に使っていたのは挿入ソートです。速度はリストの総数の2乗となります。今度はN×logNの速度のクイックソートを作ってみることにしましたが、見事に失敗しました。誰もが落ち入りやすい失敗のように思えたのであえて掲載します。
そもそも私はクイックソートというものを勘違いしていました。必ずしもN×logNにならないクイックソートがなぜ速いのかも考えもせず、図解だけを見て作ったのがいけなかったようです。クイックソートが速いのは、“必ずしもデータを移動しない”ことでした。それをご丁寧にリストを仕分け、いったんストックしておいて、あとで順番に処理していくという方法をとったために遅くなってしまったようです。
（ある方が、アップルスクリプトで組んだ、クイックソートの計測タイムを教えてくれていました。もし、それがなければ「こんなものなのか」と思っていたかもしれません。情報提供に感謝します。）
以下がこのスクリプトで3桁の数値のソートに要した時間です。
1000要素 1〜2秒
5000要素 9〜10秒
10000要素 21秒前後
global aList, list_1, list_2, list_1Ref, list_2Ref, stackNum, currentStackNum, stackListRef, aList, aListRef, sortList, sortListRef
set {sortList, aList, list_1, list_2, stackList, stackNum, currentStackNum} to {{}, {}, {}, {}, {}, 0, 1}
set {sortListRef, aListRef, list_1Ref, list_2Ref, stackListRef} to {a reference to sortList, a reference to aList, a reference to list_1, a reference to list_2, a reference to stackList}
set n to {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
set theList to {}
set theListRef to a reference to theList
repeat 1000 times
set end of theListRef to (some item of n) * 100 + (some item of n) * 10 + (some item of n)
end repeat
set T to current date
qSort(theList)
--(current date) - T
on qSort(theList)
set sortList to {}
set countTheList to count theList
push(theList)
repeat while (count sortListRef) < countTheList
set aList to picup()
set countAList to count aListRef
if countAList = 1 then
set end of sortListRef to item 1 of aListRef
else
set i to 2
set {list_1, list_2} to {{}, {}}
set pItem to item 1 of aListRef
repeat countAList - 1 times
if pItem > item i of aListRef then
set end of list_1Ref to item i of aListRef
else
set end of list_2Ref to item i of aListRef
end if
set i to i + 1
end repeat
if list_2 is not {} then push(list_2)
push({pItem})
if list_1 is not {} then push(list_1)
end if
end repeat
return sortList
end qSort
on push(aItem)
if stackNum < currentStackNum then
set end of stackListRef to aItem
set {stackNum, currentStackNum} to {stackNum + 1, currentStackNum + 1}
else
set item currentStackNum of stackListRef to aItem
set currentStackNum to currentStackNum + 1
end if
end push
on picup()
if currentStackNum > 1 then
set currentStackNum to currentStackNum - 1
return item currentStackNum of stackListRef
else
return false
end if
end picup
