ソートロジック大会

[河川屋]

＞このソートのアルゴリズム名は？
度数ソートの変形。
というか、08月27日(土) に私が書いたQuicksort改４と方針は同じ。


＞前提条件
＞ホストコンピュータ又はCOBOLで作成したデータをソートする用途向きの簡略版です。？
「ホストコンピュータでFORTRANで作成したデータ」というのは、
・ホストコンピュータ又はCOBOLで作成したデータ
という条件を満たしていますが、ソートできませんよ。
理由：FORTRANでは数値の最高位より左の桁はゼロでなくスペースとなる。コレに対応していない。
　　　また、Ｅ変換やＧ変換で書き出したデータは、左から判断していく方法ではそもそも整列できない。
　　　COBOLで作成した数値データでも、マイナスがあった場合には対応していない。



N88BasicやQuickBasicでは、基本命令の動きの違いで、このプログラムは動きません。

Function GigaSort(xNo As Integer, xFileName As String)As Integer
　　：
　　　FN=Wk + Str$(j)

まず、コレがアウト。
jは０～９のいずれかというのがプログラムの要請ですが、
Str$(0)=" 0"
となるから、ファイル名にスペースが割り込んでしまうのでDOSではダメ。
ここは、
FN=Wk + Hex$(j)

Sub SortOut(xFileName As String)
　　Open xFileName For Input　As #1
　　Field #1, LineLength　　　　'バイト数
　　While (Eof(1)=0)
　　　Get #1, -1, StrBuf
　　　Put #2, -1, StrBuf


ファイル操作については、全くのMicrosoftBasic非互換といってもよいでしょう。
Open xFileName For Input(OUTPUT/APPEND)
というふうにシーケンシャルモード（テキストファイルモード）でファイルをOPENした場合、
FIELD文やGET(PUT)文は使えません。
また、ランダムファイルとしてOPENしたとしても、
　　Open xFileName As #1 LEN=Linelength　（または OPEN "R",#1,xFileName,Linelength)
　　'　 ↑この構文はN88Basic不可。N88はLEN=256に固定。
　　Field #1, LineLength as StrBuf
　　for rec=1 to LOF(1)/Linelength　'（　N88はfor rec=1 to LOF(1)　）
　　　Get #1
　　　Lset StrBuf2=StrBuf2　　'←　　Field #2, LineLength as StrBuf2と宣言してあるとして。
　　　Put #2
と、こうなります。


あと、メモリー内に引き込めないほど多量のデータをソートするときは、
普通はマージソート（外部ソート）を使います。
「外部ソート」or「バランスウェイマージソート」or「ポリフェーズマージソート」
で検索してみてください。
大まかなやり方は以下のとおり。
１．メモリーに引き込めるだけのデータを読み込み、ソートしてからファイルに書き出す。
　　（ソートアルゴリズムはクイックなりヒープなり、速いものならどれでも可）
２．まだデータが残っていれば、１．を繰り返す。
３．ファイル同士でマージソート。

こうすることで、データの特殊性に依存せずソートできますが、
・度数ソート、逆写像ソート、ラディックスソートはＯ(n)
・マージソート、クイックソート、ヒープソートはＯ(nlogｎ)
であるので、一般論としては、度数ソートでokなら度数ソートのほうが速いといういことになります。



omasuさん　09月24日
＞①．一番遅いはずの、バブルの進化がクイックソート？。
そのとおり。

＞②．シェルソートは、選択法で作ると遅い、挿入法だとなぜか早い。
選択法で作ったシェルソートというのは聞いたことないです。
また、私のコーディングは、挿入法ベースですけど。

選択法の進化系ですが、
最小（大）値選択法－トーナメント法－ヒープ。
　※トーナメント法：
　　勝ち抜き戦で１位を決めるにはｎ－１試合必要。では、２位を決めるには？
　　　改めて残りチームで勝ち抜き戦をやっているのが最小値選択法。
　　　でも、１位に負けたチームだけ、元のトーナメント表どおりに
　　　試合すれば２位は決まるから、logｎ回で２位は決まります。
　　　３位以下も同様。よって、ＮｌｏｇＮでソートできることの証明終わり。

交換法（バブル）を元にしたシェルソートというのなら存在します。

共立出版　「プログラム書法、1976」 B.W.Kernighan and P.J.Plauger　P191
から言語を変換(元はFORTRAN)し、コメントを追加したもの。
　　　SUB SHELL(X(),N)
　　　IGAP=N
　　　DO WHILE IGAP>1
　　　　IGAP=IGAP/2　　 'shell
　　　' IGAP=IGAP/1.3　 'comb
　　　　IMAX=N-IGAP
　　　　DO
　　　　　IEX=0
　　　　　FOR I=1 TO IMAX
　　　　　　IPULUSG=I+IGAP
　　　　　　IF X(I)<=X(IPULUSG) THEN
　　　　　　　W=X(I) : X(I)=X(IPULUSG) : X(IPULUSG)=W
　　　　　　　IEX=1
　　　　　　 END IF
　　　　　NEXT
　　　　LOOP WHILE IEX=1　　　　　　　'shell
　　　' LOOP WHILE IGAP=1 AND IEX=1　 'comb
　　　LOOP
　　　END SUB

※REM文２箇所を入れ替えるとコムソート。


＞③．単純挿入法はバイナリサーチで挿入ポイントを決めると早い。
交換回数は単純挿入法と等しいから、手間をかけた割には速くならない
というのが通常の評価です。
また、シェカー法というのは輪をかけてとんでもない方法で、反面教師としてしか使えません。
シェル法以上に複雑なプログラムですが、単純挿入法にすら勝てないから。

＞シェル法のギャップのとり方
1,4,13,....M,3M+1　の他に、
1,3,7,15...M,2M+1　とか、（これもクヌース大先生おすすめ）
IGAP=IGAP*0.45　※最後はIGAP=1を実行するのをお忘れなく。
というのもおすすめ品。

＞いろんなロジックを教えてください。
単純挿入法ベースのコムソート（コムソートの性格上、最後の仕上げがバブルでないだけ。）
　　　IGAP=N
　　　WHILE IGAP > 2
　　　　IGAP = IGAP *10 \ 13
　　　　FOR i = IGAP + 1 TO N
　　　　　J = i - IGAP
　　　　　IF　Key(i) < Key(j) THEN
　　　　　　W=Key(i) : Key(i) = Key(j) :Key(j)= W
　　　　　 End If
　　　　NEXT
　　　WEND
　　　For i=2 to N
　　　 X=Key(i) : Key(0)=X
　　　 j=i-1
　　　 While X<Key(j)
　　　　 Key(j+1)=Key(j): j=j-1
　　　 Wend
　　　 Key(j+1)=X
　　 Next


マティさん　09月24日
＞クイック派に転向
そう単純に割りきれないところがあります。だからヒープ派というのが厳然として存在。
（私はシェル派なんだけどね。）
クイックソートには欠点があり、
　X=Key((L+R)\2)
とした場合、元データがたとえばこういう場合にボロボロになります。

＜1 3 5 7 9 10 8 6 4 2 ＞　（両端に小さい数、真ん中に大きい数。）

最悪時にはスタックオーバーで自爆。自爆しないためには、08月27日の私の記述の改１。
ただし、これだけでは、ｎ^2の時間がかかってしまうので、解除（厳密な解除ではない）には改３が必要。


>バブルソートの進化系はコムソート
バブルソートの最終進化系はクイックで間違いありません。
コムソートは、単純挿入法改もアリ。そして、バブルソート改より速い筈。（キーの長さが短かいならば。）


なお、個人の趣味（＝美意識）になってしまうけど、

omasuさんのように、
　 '単純挿入法
　　For i=1 To E
　　　　For j=i To 1 Step -1
　　　　　　If KeyTable(j)<KeyTable(j-1) Then
　　　　　　　 Swap KeyTable(j),KeyTable(j-1)
　　　　　　Else
　　　　　　　 Exit For
　　　　　　EndIf
　　　　Next j
　　Next i
というのは組む気ナシです。
単純挿入法は、あくまで、
　　　For i=2 to N
　　　 X=Key(i) : Key(0)=X
　　　 j=i-1
　　　 While X<Key(j)
　　　　 Key(j+1)=Key(j): j=j-1
　　　 Wend
　　　 Key(j+1)=X
　　 Next
であって、Exit Forのようなムナくそ悪い「例外処理命令」は使いたくないです。



Zgockさん　09月29日

＞２回に分割する場合、バケツソート（注：度数ソート）に比べて速度は２倍、ワークは１００分の１
速度は１／２です。

＞クイックソートは速いアルゴリズムで非常に美しいですが、
＞安定じゃないのだけが欠点ですね。
＞そういう理由からヒープソートをよく使います。
これって、「ヒープソートは安定である」という意味にしか解釈できないのですが。
でも、ヒープソートって安定なんか？
平成１５年度ソフトウェア開発技術者試験午前問13では、「ヒープソートは安定ではない」
が正解なんですけど。
http://sinzo.web.infoseek.co.jp/joho/so ... 03_01.html
クイックソートは、「n^2の時間がかかる数列が存在する」
というのが最大の欠点でしょ？

[マティ]

omasuさんへ
①テストデータは、貴殿作成のプログラムで作成しました。
②AB4.1で実行して下さい。
③AB4.1(.abpにコピー)で大丈夫だとおもいます。エラーが出たらご報告ください。
PS.現状の仕様でよければ10倍は早いロジックを作成中です。

会社の都合で、ここ３年程ホスト系のプログラム作成とメンテナンスをしていました。
一番プログラムを作成したのはMASMだったりします。

酒は死ぬほど大好きですが、この間は久しぶりに飲んだので暴走してしまいました。皆さんごめんなさい

河川屋さんへ
Quicksort改４ですね！たしかに提案を受けていました。ありがとうございます
言い訳
一文字単位でグループ化して行けば、ソートが完成するな・・・って考えていたら度数ソート？が出来たのですが、あまりにも遅いので途中から普通のソートと組み合わせる方法にして作成しました。
そしたら河川屋さんの提案通りの組み合わせになっていました。

前提条件
たしかに間違えています。申し訳ありません。
COBOLで作成したデータを固定長ファイルのテキストデータ形式でコンバートした場合かつ数値項目（正の数）、のみとさせて頂きます。
また、今回のテストデータ用に作成したので、他の条件は一切考慮していませんでした。

他ベーシック対応
最近は、ExcelのVBAやVB6しかベーシック系の言語は使用していないのですが・・・
移植系の話をするなら、私がABで作成しているプログラムは基本的にポインターを使用しています。
ポインターが無かったらABはやっていません。
VBで巨大はバイト型の配列を作成すると同様な処理ができるので問題ないと言えばそれまでですが・・・
（実際自分もABを使用するまでは、バイト型の配列を使用していました）

①ファイル名については（カタカナソート対応の為に）Chr$で対応済みです。
②ファイル操作について、AB4.1で Line Input が使用できれば、こんなロジックにする必要も無かったのですが・・・（可変長対応になるし・・・）
③巨大ファイルを操作する場合はマージソートを使用するのは分かっていますが・・・そのうち投稿します。

河川屋さんへ質問
名指しで申し訳ありませんが、お教えください。
極論すると全てのソートは、バブルソートの進化系ってなりませんか？
バブルとコムとシェルは、ほぼ同じロジック。クイックも同系列
度数ソートは先頭文字で振り分けるから、クイックの進化系？
バブルソートの進化系じゃないソートってどのようなソートがあるのですか？
（論理的な教育を受けていないので、よく分からないのです）

文字列について
最後にABは文字列処理や異常に遅いので、なるべく文字列処理を無くしています。

[マティ]

指摘を受けた部分は大体修正しましたので、お試しください。

ここをクリックするとコードが表示されます [ここをクリックすると内容が表示されます]

[omasu]

　いつも大変お世話になっております。

　皆様のアルゴリズムの豊富さと高度なロジック、ありがたいご指導に感謝しております。

　ただいま、悪戦苦闘の毎日です。

　当初、アクティブベーシックＡＢ２．６２で作成していたロジックも、ＡＢ最新版で実行可能となりました、
　これも、皆様のおかげです。

標題について

　当初のＡＢ２．６２での文字列交換法から数値交換法に変更しても、劇的な変化が見られなかったこと、
　４．ＸＸにしたとたん、かなりのスピードアップが実現したこと、
　これらにずっと疑問を抱いておりました。

　バージョンの違いにより、数値交換、文字列交換がどれだけ違うのか、ベンチマークテストを実施しました。
　（書籍に載っているような数々の試験はしていません、あくまでも数値と、文字の交換が対象です）

ここをクリックするとベンチマークテスト結果が表示できます。 [ここをクリックすると内容が表示されます]

以上のことから
　ＡＢ２．６２とＡＢ４．１０との速度比は
　　・数値交換は　　約１７００倍
　　・文字列交換は　約　　　８倍

　同一バージョン内の数値交換と文字列交換の速度比は
　　・ＡＢ２．６２は　約１．４倍
　　・ＡＢ４．１０は　約３００倍

数値交換については、かなりのスピードアップがされていることが測定できました。

記事：
　当然のことながら、当初のＡＢ２．６２（文字列交換法）３２秒をバージョンアップすると８倍の４秒
　　　　　　　　　　それを、数値交換法にすると１３ｍｓにはなりませんが
　今回プロジェクトの速度比較はしておりません。
　プロジェクトで作成した速度にも違いがあるように思えますが、また悩んでしまいました。
追伸：
　それでも、ＡＢ２．６２は手放せないですよね！（ＡＢ２．６２ユーザより）（ＡＢ２．７？、ＡＶＢ、ＡＣ）

[omasu]

お世話になります。

　シェルソートについて、
河川屋さんのありがたいご指導のなかに

＞シェル法のギャップのとり方
1,4,13,....M,3M+1　の他に、
1,3,7,15...M,2M+1　とか、（これもクヌース大先生おすすめ）
IGAP=IGAP*0.45　※最後はIGAP=1を実行するのをお忘れなく。
というのもおすすめ品。

という一文がありました。
いろいろ思考錯誤と試行を繰り返しましたが、
　①．ギャップのとり方で速度がかなり変わる
　②．ギャップの初期値のとり方でも速度が違う
そのため。ギャップの初期値について研究した結果、発見がありました。

調査方法：一万件のソートを一万回実施（推定実行時間一回１秒の場合一万秒≒２．７７時間かかります）（２秒だと、３秒だと・・・）
　　　　　一万回のギャップ初期値を１万から１ずつ減らし１になるまで実行（睡眠中に愛機が実行してくれた）(^o^)
　　　　　※本来はデータ件数の外側にも最適数値が存在する可能性があります。
　　　　　　今回はギャップを３で割っているため、３倍の３万回を実施する必要があります。（今回は内側のみの調査です）
その結果、一番早かった初期値が「件数×０．８９７５」でした。。(この初期値もクヌース大大先生のおすすめかも知れませんが）

[ここをクリックすると内容が表示されます]

実行については　　　　　　　「２００５年９月２５日（日）」の「マティさんに返信」のソート部を入替えてください。
テストデータ作成方法は　　　「２００５年９月２５日（日）１０」の「テストデータの掲示についてⅡ」参照

今まで、実行できたロジックの速度も掲示します。
しかし、５０万件のソートは愛機の環境が不安定になり測定時間も不安定になることから計測を断念しました。

ここをクリックすると実行速度比較が表示されます。 [ここをクリックすると内容が表示されます]

追伸１：マティさんのクイック改４（８００万件）ですが、１万件まではすばらしい速度で実行しますが、
　　　　５万件からかなり待っても終了しません、実行終了時間が不明のため、断念しています。（推定時間を教えてください）
追伸２：シェルとコムの違いに今悩んでいます。
追伸３：申し訳ありません、イグトランスさんのソートキー指定が実力不足でいまだに、コンパイルエラーとなっております。
　　　　前回のコードの部分提示を、コード全体提示に修正していただけませんでしょうか。
追伸４：今回の調査はたった１万件を１万回実施したのに過ぎず精度はいいかげんです、
　　　　スーパーコンピューター等で大量件数を大量回実行すればどんな件数でも対応する初期値が出ると思います。
追伸５：ギャップの減らし方についても調査が必要と思われます。

[マティ]

2005年09月28日(水)に投稿を行ったロジックではなく！
2005年09月29日(木)に再投稿を行ったロジックをご使用下さい。
また
Ｃ：ドライブのルートにｔｍｐフォルダーを作成して下さい。
c:\tmp\

[omasu]

お世話になります。

シェル法についてⅡ
　河川屋さんのギャップの減らし方「ギャップ×０．４５」（クヌース大大大先生おすすめ）を実施、最速値を記録しました。
>>>IGAP=IGAP*0.45　※最後はIGAP=1を実行するのをお忘れなく。というのもおすすめ品。
（ほんとにギャップの減らし方にも最速値があることを実感しました。）

[ここをクリックすると内容が表示されます]

ここをクリックすると実行速度比較が表示されます。 [ここをクリックすると内容が表示されます]

[ar]

ソートアルゴリズムごとの実際の評価は大変興味深く拝見させてもらっています。
ただマージソートに関してはまだ評価されていないようなので下記ソースを投稿させて貰います（C言語アルゴリズム辞典からの写しですけど･･･）。
とりあえずパフォーマンス評価の一つにしていただけたらと思います。

コード: 全て選択

Const N = 100000		'データ個数
Type MERGESORT
	key As *Byte		'キーデーター
	info As *Byte		'csvファイルの行データ
End Type
Dim a[N - 1] As MERGESORT
Dim work[(N - 1)/ 2 + 1] As MERGESORT

'マージソート
'	first : 整列範囲の最小配列添え字
'	last  : 整列範囲の最大配列添え字
Sub mergesort(first As Long, last As Long)
	Dim middle As Long
	Dim i As Long
	Dim j As Long
	Dim k As Long
	Dim p As Long

	If first < last Then
		middle = (first + last) \ 2
		'再起呼び出し
		mergesort(first, middle)
		mergesort(middle + 1, last)
		'
		p = 0
		i = first
		Do
			work[p] = a		'同じ構造体であれば等号でOK
			p = p + 1
			i = i + 1
		Loop Until i > middle
		i = middle + 1
		j = 0
		k = first
		While i <= last And j < p
			If lstrcmp(work[j].key, a.key) <= 0 Then	'数値比較の場合は work[j].key <= a.key
				a[k] = work[j]
				k = k + 1
				j = j + 1
			Else
				a[k] = a
				k = k + 1
				i = i + 1
			End If
		Wend
		While j < p
			a[k] = work[j]
			k = k + 1
			j = j + 1
		Wend
	End If
End Sub

[omasu]

お世話になります。
　ついに登場、マージソート！！
　ついに登場、久々の新メンバーに感動しております。（自動的にメンバー登録されます）(~o~)

何度もチャレンジ
申し訳ありません。
　どうやって使えばいいか面食らっています？？？？？？？。

　ＣＳＶを読み込み、そのデータからキー列を抜いて、そのキーを、
　ａ［］に放り込んでから、Ｗｏｒｋ［］を使って・・
　０から？、１から？・Ｎは実データ数？・・、　．Ｋｅｙ？・・・・

　もうしばらくか、だいぶ、時間をいただくか、実行可能な環境までお教えくだされば幸いです。

追伸：マティさんのプライベートメッセージの補助で８００万件のソートが
　　　ついに動きました。（私の愛機の記憶力の限界値と設定を適正化）
　　　次回、実行時間を乞うご期待！

[ar]

失礼、説明が無かったですね。
マージソートは名前の通りデーターを順にマージ(併合)することで整列を行います。ただし、そのためには一旦データを展開する作業スペースが必要で、それがwork配列です。実際のデータはa配列に格納します。今回の場合、列の情報(info)と比較用のキー(key)を構造体として持たせています。
ですので、順序としては、
　1)ファイルの読み込み
　2)a[].infoにデータを格納
　3)a[].infoの先頭2列分のデータを連結してa[].keyに格納
　4)mergesort(0、N-1)で全域を整列
　5)結果の出力
となります。
下のコードは私が動作検証のために使ったものです。ソースコードと同じフォルダ内の"testcsv.csv"を読み込み、"result.csv"として出力するものです。前回投稿したマージソートの下にコピペすれば使えるはずです。処理数を定数Nでふるのと、pathを変えれば評価くらいには使えますかね。

コード: 全て選択

Dim i As Long
Dim j As Long
Dim time As SYSTEMTIME
Dim offset As Long
Dim path[MAX_PATH] As Byte
Dim hFile As HANDLE
Dim flen As DWord
Dim file As *Byte

'ファイルの読み込み
Print "read";
GetCurrentDirectory(MAX_PATH, path)
lstrcat(path, "\testdata.csv")
hFile = CreateFile(path, GENERIC_READ, 0, ByVal NULL, OPEN_EXISTING, FILE_FLAG_SEQUENTIAL_SCAN, 0)
flen = GetFileSize(hFile, 0)
file = calloc(SizeOf(Byte) * flen + 1)
Print ReadFile(hFile, file, flen, VarPtr(flen), ByVal NULL)
CloseHandle(hFile)

'行ごとに分解
Print "sepalate"
a[0].info = VarPtr(file[0])
i = 1
j = 0
Do
	Select Case file[j]
		Case 13, 10				'CR or LF
			file[j] = 0
			If file[j + 1] = 10 Then
				file[j + 1] = 0
				j = j + 1
			End If
			a.info = VarPtr(file[j + 1])
			i = i + 1
	End Select
	j = j + 1 
Loop While j < flen Or i < N

'キーの作成
i = 0
Do
	a.key = calloc(SizeOf(Byte) * 10 + 1)
	memcpy(VarPtr(a.key[0]), VarPtr(a.info[0]), 5)
	memcpy(VarPtr(a.key[5]), VarPtr(a.info[6]), 5)
	i = i + 1
Loop While i < N

'整列
Print "marge-sort",
GetLocalTime(time)
Print time.wMinute; ":"; time.wSecond; ":"; time.wMilliseconds; " -> ";
mergesort(0, N - 1)
GetLocalTime(time)
Print time.wMinute; ":"; time.wSecond; ":"; time.wMilliseconds

'結果の出力
Print "write",
GetCurrentDirectory(MAX_PATH, path)
lstrcat(path, "\result.csv")
Open path For Output As #1
i = 0
Do
	Print #1, MakeStr(a.info)
	i = i + 1
Loop While i < N
Close #1
free(file)

このままだと、動的な配列の確保がしにくいなぁ･･･ということで、Publicなデータを持つクラスをNewで生成するのがいいのだろうか？

[omasu]

お世話になります。

マティさんの８００万件のソートについて

　ついに最大ソート件数８００万件のソートが実証できました。
　※マティさんのプライベートメッセージのサポートのおかげです。
　　・私の愛機の環境では「Const xReSort=51200'まとめてソートする行数」が追いつかず、
　　　迷宮の世界に入っていました。
　　・「xReSortの値は2048の倍数で設定して下さい」
　　　メモリ２５６ＭＢでは、「２０４８０」で実行が可能となりました。

ａｒさんのマージソートについて

　ついに１０万件ソートが１秒をきりました。
　すばらしい速度に感動しております。

　※ａｒさんの「動的な配列の確保がしにくい」というメッセージに同感しています。
　　ぜひ「Ｎ」の値を自動化していただきたいと要望をいたします。


さて、実行時間の件ですが、どうも、私のテストデータの作りと前提条件の記述の悪さが災いしたようで、
「５桁のランダム数字を文字列として扱い」と書いております。申し訳ありません。
　速度比較を「５桁のランダム数字も５桁のランダム文字もソート可能」と「５桁のランダム数字がソート可能」に分けて表示をいたします。

ここをクリックすると実行速度比較が表示されます。 [ここをクリックすると内容が表示されます]

[omasu]

大変申し訳なく思っています。

　今回のテストデータの提示と前提条件の提示について、

　紛らわしい表現があったことを深くお詫び申し上げます。

テストデータとして英数カナ混在データ作成のプログラムを掲示します。

[ここをクリックすると内容が表示されます]

[マティ]

omasuさんマティです!!!
クイック改４は、ソートの対象を制限していません。!!!
文字コード順なら大体のソートは可能です（半角カナが混じると保証できませんが・・・）

そういう訳で、分類の変更をお願いします。

[omasu]

> クイック改４は、ソートの対象を制限していません。!!!
> 文字コード順なら大体のソートは可能です（半角カナが混じると保証できませんが・・・）

申し訳ありません。

　全ての出力ファイルを確認したはずが見落としていました。
　　クイック改４の出力ファイルはＯｕｔｐｕｔ．ｃｓｖでした。
　　　前回の実行時間一覧の分類を訂正します。

[ar]

前回最後にコメントした動的な確保は下記のようなのでどうですか？
omasuさん提供のテストデータ作成プログラムで作ったデータを使って、n列分のソートを行うようになっています。ついでに、ソート関数にデータを渡すようにしたので関数内外でのデータのネーミングを意識しないですむので、再利用しやすいのではと。
一応、100万件までの動作はしました。100万件動作時でメモリの消費量は約23MB。800万件は相当な覚悟が必要かも･･･
ここまでくると、キーの作成と書き出し時間が相当長くなっている。

コード: 全て選択

#N88BASIC

Class CSVSORT
Public
	keystr As *Byte						'文字列比較用キーデータ
	info As *Byte						'列位置
End Class
Dim data As *CSVSORT					'データ配列
Dim work As *CSVSORT					'展開用配列
Dim rcd_len As Long						'レコード長(改行含まず)
Dim rcd_max As Long						'データ(レコード)の最大数

Dim n As Long							'読み込みデータ数
Dim i As Long
Dim time As SYSTEMTIME
Dim path[MAX_PATH] As Byte
Dim hFile As HANDLE
Dim flen As DWord
Dim file As *Byte

'初期化
rcd_len = (5 + 1) * 26					'(文字列5文字 + カンマ) * 26列

'ファイルの読み込み
Print "read"
GetCurrentDirectory(MAX_PATH, path)
lstrcat(path, "\infile1000000.csv")
hFile = CreateFile(path, GENERIC_READ, 0, ByVal NULL, OPEN_EXISTING, FILE_FLAG_SEQUENTIAL_SCAN, 0)
flen = GetFileSize(hFile, NULL)
rcd_max = (flen + 1) / (rcd_len + 2)

'データ個数の決定と確保
Input "record number =?", n
If n < 1 Or n > rcd_max Then n = rcd_max
data = New [ELM(n)] CSVSORT
work = New [ELM(n) \ 2 + 1] CSVSORT

'行ごとに分解(ファイルポインタの位置のみ)とキーの作成
Print "input data & make keys"
file = calloc(SizeOf(Byte) * 5 + 1)
i = 0
Do
	data.info = i * (rcd_len + 2)
	data.keystr = calloc(SizeOf(Byte) * 10 + 1)
	SetFilePointer(hFile, data.info, NULL, FILE_BEGIN)
	ReadFile(hFile, file, 5, VarPtr(flen), ByVal NULL)
		lstrcpy(data.keystr, file)
	SetFilePointer(hFile, 1, NULL, FILE_CURRENT)
	ReadFile(hFile, file, 5, VarPtr(flen), ByVal NULL)
		lstrcat(data.keystr, file)
	i = i + 1
Loop While i < n
free(file)

'整列
Print "marge-sort",
GetLocalTime(time)
Print time.wMinute; ":"; time.wSecond; ":"; time.wMilliseconds; " -> ";

mergesort_str(0, n - 1, data)					'文字列として比較

GetLocalTime(time)
Print time.wMinute; ":"; time.wSecond; ":"; time.wMilliseconds

'結果の出力
Print "write",
GetCurrentDirectory(MAX_PATH, path)
lstrcat(path, "\result.csv")
Open path For Output As #1
file = calloc(SizeOf(Byte) * rcd_len + 1)
i = 0
Do
	SetFilePointer(hFile, data.info, NULL, FILE_BEGIN)
	ReadFile(hFile, file, rcd_len, VarPtr(flen), ByVal NULL)
	Print #1, MakeStr(file)
	i = i + 1
Loop While i < n
Close #1
free(file)
CloseHandle(hFile)

Delete data
Delete work
Print "end"

'マージソート
'	first	: 整列範囲の最小配列添え字
'	last	: 整列範囲の最大配列添え字
'	a		: データ
Sub mergesort_str(first As Long, last As Long, a As *CSVSORT)
	Dim middle As Long
	Dim i As Long
	Dim j As Long
	Dim k As Long
	Dim p As Long

	If first < last Then
		middle = (first + last) \ 2
		'再起呼び出し
		mergesort_str(first, middle, a)
		mergesort_str(middle + 1, last, a)
		'
		p = 0
		i = first
		Do
			work[p].keystr = a.keystr
			work[p].info = a.info
			p = p + 1
			i = i + 1
		Loop Until i > middle
		i = middle + 1
		j = 0
		k = first
		While i <= last And j < p
			If lstrcmp(work[j].keystr, a.keystr) <= 0 Then
				a[k].keystr = work[j].keystr
				a[k].info = work[j].info
				k = k + 1
				j = j + 1
			Else
				a[k].keystr = a.keystr
				a[k].info = a[i].info
				k = k + 1
				i = i + 1
			End If
		Wend
		While j < p
			a[k].keystr = work[j].keystr
			a[k].info = work[j].info
			k = k + 1
			j = j + 1
		Wend
	End If
End Sub