■非再帰QuickSort（カンニング編

と、いう事でここは先人の経験と技術を素直に学ばせていただこう。
#決してカンニングではない..と思う（多分 X)

残念ながら出典サイトはなくなってしまいました。
確か「Excel VBA 実用サンプルコレクション」著者 渡辺ひかる氏のサイト（www.vbasekai.com）に、
以前mougでよく回答してらっしゃった工藤氏のコードが載ってたと思う。
それを参考にさせて頂きました。感謝。

Option Explicit

Private Declare Function timeGetTime Lib "winmm.dll" () As Long
Private QS() As String　　　　'ソートデータ用
Private QL() As Long　　　　　'ソートインデックス用
'-------------------------------------------------
Private Sub test()　　　　　　'テストプロシージャ選択用
　　Const cnt As Long = 65536 'テストデータ量
　　Dim ret() As String　　　 '書出し用配列
　　Dim t(1)　As Long
　　Dim i　　 As Long
　　Dim p　　 As Long
　　Dim v

　　ReDim QS(1 To cnt)
　　ReDim QL(1 To cnt)
　　ReDim ret(1 To cnt, 0)

　　For Each v In Range("A1").Resize(cnt).Value
　　　　i = i + 1
　　　　QL(i) = i
　　　　QS(i) = v
　　Next

　　p = 1
　　t(0) = timeGetTime
　　Select Case p
　　Case 1
　　　　Call LQuickSort(1, cnt)
　　Case 2
　　　　Call LQuickSortS(1, cnt)
　　Case 3
　　　　Call LQuickLoop4
　　End Select

　　For i = 1 To cnt
　　　　ret(i, 0) = QS(QL(i))
　　Next

　　t(1) = timeGetTime
　　'Sheets.Add.Range("A1").Resize(cnt).Value = ret
　　Erase QS, QL, ret
　　Debug.Print cnt, t(1) - t(0)
End Sub
'-------------------------------------------------
Private Sub LQuickSort(n As Long, x As Long) '再帰
　　Dim tmp As String
　　Dim i　 As Long
　　Dim j　 As Long
　　Dim k　 As Long

　　i = n
　　j = x
　　tmp = QS(QL((i + j) ¥ 2))

　　Do
　　　　Do While QS(QL(i)) < tmp
　　　　　　i = i + 1
　　　　Loop
　　　　Do While tmp < QS(QL(j))
　　　　　　j = j - 1
　　　　Loop

　　　　If j <= i Then
　　　　　　Exit Do
　　　　End If
　　　　k = QL(i)
　　　　QL(i) = QL(j)
　　　　QL(j) = k
　　　　i = i + 1
　　　　j = j - 1
　　Loop

　　If n < (i - 1) Then
　　　　LQuickSort n, i - 1
　　End If
　　If (j + 1) < x Then
　　　　LQuickSort j + 1, x
　　End If
End Sub
'-------------------------------------------------
Private Sub LQuickSortS(n As Long, x As Long) '再帰
　　Dim tmp As String
　　Dim i　 As Long
　　Dim j　 As Long
　　Dim k　 As Long

　　tmp = QS(QL((n + x) ¥ 2))
　　i = n - 1
　　j = x + 1

　　Do
　　　　Do
　　　　　　i = i + 1
　　　　Loop While QS(QL(i)) < tmp
　　　　Do
　　　　　　j = j - 1
　　　　Loop While tmp < QS(QL(j))

　　　　If j <= i Then
　　　　　　Exit Do
　　　　End If
　　　　k = QL(i)
　　　　QL(i) = QL(j)
　　　　QL(j) = k
　　Loop

　　If n < (i - 1) Then
　　　　LQuickSortS n, i - 1
　　End If
　　If (j + 1) < x Then
　　　　LQuickSortS j + 1, x
　　End If
End Sub
'-------------------------------------------------
Private Sub LQuickLoop4()　　 '非再帰
　　Const p　　 As Long = 100 '記憶用配列サイズ
　　Dim idxi(p) As Long　　　 'Index記憶用
　　Dim idxj(p) As Long　　　 'Index記憶用
　　Dim Lv　　　As Long　　　 '深さレベル
　　Dim mn　　　As Long
　　Dim mx　　　As Long
　　Dim i　　　 As Long
　　Dim j　　　 As Long
　　Dim k　　　 As Long
　　Dim tmp　　 As String

　　Lv = 1
　　idxi(Lv) = LBound(QL)
　　idxj(Lv) = UBound(QL)

　　Do While Lv > 0
　　　　mn = idxi(Lv)
　　　　mx = idxj(Lv)
　　　　Lv = Lv - 1
　　　　tmp = QS(QL((mn + mx) ¥ 2))
　　　　i = mn - 1
　　　　j = mx + 1

　　　　Do
　　　　　　Do
　　　　　　　　i = i + 1
　　　　　　Loop While QS(QL(i)) < tmp
　　　　　　Do
　　　　　　　　j = j - 1
　　　　　　Loop While tmp < QS(QL(j))
　　　　　　If j <= i Then
　　　　　　　　Exit Do
　　　　　　End If
　　　　　　k = QL(i)
　　　　　　QL(i) = QL(j)
　　　　　　QL(j) = k
　　　　Loop

　　　　If mn < (i - 1) Then
　　　　　　Lv = Lv + 1
　　　　　　idxi(Lv) = mn
　　　　　　idxj(Lv) = i - 1
　　　　End If
　　　　If (j + 1) < mx Then
　　　　　　Lv = Lv + 1
　　　　　　idxi(Lv) = j + 1
　　　　　　idxj(Lv) = mx
　　　　End If
　　Loop
End Sub

[LQuickSort]
65536　　　　 329
65536　　　　 329
65536　　　　 328

[LQuickSortS]
65536　　　　 312
65536　　　　 297
65536　　　　 297

[LQuickLoop4]
65536　　　　 312
65536　　　　 297
65536　　　　 314

ver2010。
[LQuickSort]
1000000　　　 6907
1000000　　　 7032
1000000　　　 7017

[LQuickSortS]
1000000　　　 6766
1000000　　　 6800
1000000　　　 6781

[LQuickLoop4]
1000000　　　 6719
1000000　　　 6767
1000000　　　 6735

再帰版と同等の速さです。しかも簡潔。
達人の方が書くとこうも違うものなのですね..
他にも色々なサイトで非再帰版のコードを見て勉強させて頂きましたが、
[LQuickLoop4]の元になった工藤氏のコードが一番勉強になりました。有難うございます。

また、再帰版も再掲してますが、[LQuickSortS]は今回Loop版に合わせて比較の意味で載せました。
以前はこっち使ってたんですが、いつの間にか変わってました。[LQuickSort]のコードの方が馴染みやすいのかな..
#師匠の教えもあってちょっと修正してますが :)
それにしても、ちょっとしたコーディングの違いで差が出るもんなんですね－

あとは余談。
コードを見てもらうとわかる事なので今さらですが、今回の配列ソートは配列そのものを入れ替えずに
ソートインデックス用のLong型配列を作ってこれを入れ替えてます。
これは、セル範囲を配列に取得したVariant型２次元配列をそのままQuickSortする場合と比較して、
ソートデータ用のString型１次元配列、ソートインデックス用Long型１次元配列、
それに書出し用２次元配列にLoop処理で格納し直す処理を入れても、より高速に処理できます。