1 |
// Upgraded to Delphi 2009: Sebastian Zierer
|
2 |
|
3 |
(* ***** BEGIN LICENSE BLOCK *****
|
4 |
* Version: MPL 1.1
|
5 |
*
|
6 |
* The contents of this file are subject to the Mozilla Public License Version
|
7 |
* 1.1 (the "License"); you may not use this file except in compliance with
|
8 |
* the License. You may obtain a copy of the License at
|
9 |
* http://www.mozilla.org/MPL/
|
10 |
*
|
11 |
* Software distributed under the License is distributed on an "AS IS" basis,
|
12 |
* WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
|
13 |
* for the specific language governing rights and limitations under the
|
14 |
* License.
|
15 |
*
|
16 |
* The Original Code is TurboPower SysTools
|
17 |
*
|
18 |
* The Initial Developer of the Original Code is
|
19 |
* TurboPower Software
|
20 |
*
|
21 |
* Portions created by the Initial Developer are Copyright (C) 1996-2002
|
22 |
* the Initial Developer. All Rights Reserved.
|
23 |
*
|
24 |
* Contributor(s):
|
25 |
*
|
26 |
* ***** END LICENSE BLOCK ***** *)
|
27 |
|
28 |
{*********************************************************}
|
29 |
{* SysTools: StSort.pas 4.04 *}
|
30 |
{*********************************************************}
|
31 |
{* SysTools: General purpose sorting class using *}
|
32 |
{* merge sort algorithm *}
|
33 |
{*********************************************************}
|
34 |
|
35 |
{$I StDefine.inc}
|
36 |
|
37 |
{Notes:
|
38 |
The sequence to sort data is this:
|
39 |
|
40 |
Sorter := TStSorter.Create(MaxHeap, RecLen);
|
41 |
Sorter.Compare := ACompareFunction;
|
42 |
repeat
|
43 |
... obtain ADataRecord from somewhere ...
|
44 |
Sorter.Put(ADataRecord);
|
45 |
until NoMoreData;
|
46 |
while Sorter.Get(ADataRecord) do
|
47 |
... do something with ADataRecord ...
|
48 |
Sorter.Free;
|
49 |
|
50 |
While Put is called, the sorter buffers as many records as it can fit in
|
51 |
MaxHeap. When that space is filled, it sorts the buffer and stores that
|
52 |
buffer to a temporary merge file. When Get is called, the sorter sorts the
|
53 |
last remaining buffer and starts either returning the records from the
|
54 |
buffer (if all records fit into memory) or merging the files and returning
|
55 |
the records from there.
|
56 |
|
57 |
The Compare function can be used as a place to display status and to abort
|
58 |
the sort. It is not possible to accurately predict the total number of
|
59 |
times Compare will be called, but it is called very frequently throughout
|
60 |
the sort. To abort a sort from the Compare function, just raise an
|
61 |
exception there.
|
62 |
|
63 |
The Reset method can be called to sort another set of data of the same
|
64 |
record length. Once Get has been called, Put cannot be called again unless
|
65 |
Reset is called first.
|
66 |
|
67 |
There is no default Compare function. One must be assigned after creating
|
68 |
a TStSorter and before calling Put. Otherwise an exception is raised the
|
69 |
first time a Compare function is needed.
|
70 |
|
71 |
If Create cannot allocate MaxHeap bytes for a work buffer, it
|
72 |
repeatedly divides MaxHeap by two until it can successfully allocate that
|
73 |
much space. After finding a block it can allocate, it does not attempt to
|
74 |
allocate larger blocks that might still fit.
|
75 |
|
76 |
Unlike MSORTP, STSORT always swaps full records. It does not use pointer
|
77 |
swapping for large records. If this is desirable, the application should
|
78 |
pass pointers to previously allocated records into the TStSorter class.
|
79 |
|
80 |
The OptimumHeapToUse, MinimumHeapToUse, and MergeInfo functions can be used
|
81 |
to optimize the buffer size before starting a sort.
|
82 |
|
83 |
By default, temporary merge files are saved in the current directory with
|
84 |
names of the form SORnnnnn.TMP, where nnnnn is a sequential file number.
|
85 |
You can supply a different merge name function via the MergeName property
|
86 |
to put the files in a different location or use a different form for the
|
87 |
names.
|
88 |
|
89 |
The sorter is thread-aware and uses critical sections to protect the Put,
|
90 |
Get, and Reset methods. Be sure that one thread does not call Put after
|
91 |
another thread has already called Get.
|
92 |
}
|
93 |
|
94 |
unit StSort;
|
95 |
|
96 |
interface
|
97 |
|
98 |
uses
|
99 |
Windows,
|
100 |
SysUtils, STConst, STBase;
|
101 |
|
102 |
const
|
103 |
{.Z+}
|
104 |
MinRecsPerRun = 4; {Minimum number of records in run buffer}
|
105 |
MergeOrder = 5; {Input files used at a time during merge, >=2, <=10}
|
106 |
MedianThreshold = 16; {Threshold for using median-of-three quicksort}
|
107 |
{.Z-}
|
108 |
|
109 |
type
|
110 |
TMergeNameFunc = function (MergeNum : Integer) : string;
|
111 |
|
112 |
TMergeInfo = record {Record returned by MergeInfo}
|
113 |
SortStatus : Integer; {Predicted status of sort, assuming disk ok}
|
114 |
MergeFiles : Integer; {Total number of merge files created}
|
115 |
MergeHandles : Integer; {Maximum file handles used}
|
116 |
MergePhases : Integer; {Number of merge phases}
|
117 |
MaxDiskSpace : LongInt; {Maximum peak disk space used}
|
118 |
HeapUsed : LongInt; {Heap space actually used}
|
119 |
end;
|
120 |
|
121 |
{.Z+}
|
122 |
TMergeIntArray = array[1..MergeOrder] of Integer;
|
123 |
TMergeLongArray = array[1..MergeOrder] of LongInt;
|
124 |
TMergePtrArray = array[1..MergeOrder] of Pointer;
|
125 |
{.Z-}
|
126 |
|
127 |
TStSorter = class(TObject)
|
128 |
{.Z+}
|
129 |
protected
|
130 |
{property instance variables}
|
131 |
FCount : LongInt; {Number of records put to sort}
|
132 |
FRecLen : Cardinal; {Size of each record}
|
133 |
FCompare : TUntypedCompareFunc; {Compare function}
|
134 |
FMergeName : TMergeNameFunc; {Merge file naming function}
|
135 |
|
136 |
{private instance variables}
|
137 |
sorRunCapacity : LongInt; {Capacity (in records) of run buffer}
|
138 |
sorRunCount : LongInt; {Current number of records in run buffer}
|
139 |
sorGetIndex : LongInt; {Last run element passed back to user}
|
140 |
sorPivotPtr : Pointer; {Pointer to pivot record}
|
141 |
sorSwapPtr : Pointer; {Pointer to swap record}
|
142 |
sorState : Integer; {0 = empty, 1 = adding, 2 = getting}
|
143 |
sorMergeFileCount : Integer; {Number of merge files created}
|
144 |
sorMergeFileMerged : Integer; {Index of last merge file merged}
|
145 |
sorMergeOpenCount : Integer; {Count of open merge files}
|
146 |
sorMergeBufSize : LongInt; {Usable bytes in merge buffer}
|
147 |
sorMergeFileNumber : TMergeIntArray; {File number of each open merge file}
|
148 |
sorMergeFiles : TMergeIntArray; {File handles for merge files}
|
149 |
sorMergeBytesLoaded: TMergeLongArray;{Count of bytes in each merge buffer}
|
150 |
sorMergeBytesUsed : TMergeLongArray; {Bytes used in each merge buffer}
|
151 |
sorMergeBases : TMergePtrArray; {Base index for each merge buffer}
|
152 |
sorMergePtrs : TMergePtrArray; {Current head elements in each merge buffer}
|
153 |
sorOutFile : Integer; {Output file handle}
|
154 |
sorOutPtr : Pointer; {Pointer for output buffer}
|
155 |
sorOutBytesUsed : LongInt; {Number of bytes in output buffer}
|
156 |
{$IFDEF ThreadSafe}
|
157 |
sorThreadSafe : TRTLCriticalSection;{Windows critical section record}
|
158 |
{$ENDIF}
|
159 |
sorBuffer : Pointer; {Pointer to global buffer}
|
160 |
|
161 |
{protected undocumented methods}
|
162 |
procedure sorAllocBuffer(MaxHeap : LongInt);
|
163 |
procedure sorCreateNewMergeFile(var Handle : Integer);
|
164 |
procedure sorDeleteMergeFiles;
|
165 |
function sorElementPtr(Index : LongInt) : Pointer;
|
166 |
procedure sorFlushOutBuffer;
|
167 |
procedure sorFreeBuffer;
|
168 |
procedure sorGetMergeElementPtr(M : Integer);
|
169 |
function sorGetNextElementIndex : Integer;
|
170 |
procedure sorMergeFileGroup;
|
171 |
procedure sorMoveElement(Src, Dest : Pointer);
|
172 |
procedure sorOpenMergeFiles;
|
173 |
procedure sorPrimaryMerge;
|
174 |
procedure sorRunSort(L, R : LongInt);
|
175 |
procedure sorStoreElement(Src : Pointer);
|
176 |
procedure sorStoreNewMergeFile;
|
177 |
procedure sorSwapElements(L, R : LongInt);
|
178 |
procedure sorSetCompare(Comp : TUntypedCompareFunc);
|
179 |
|
180 |
{protected documented methods}
|
181 |
procedure EnterCS;
|
182 |
{-Enter critical section for this instance}
|
183 |
procedure LeaveCS;
|
184 |
{-Leave critical section}
|
185 |
{.Z-}
|
186 |
|
187 |
public
|
188 |
constructor Create(MaxHeap : LongInt; RecLen : Cardinal); virtual;
|
189 |
{-Initialize a sorter}
|
190 |
destructor Destroy; override;
|
191 |
{-Destroy a sorter}
|
192 |
|
193 |
procedure Put(const X);
|
194 |
{-Add an element to the sort system}
|
195 |
function Get(var X) : Boolean;
|
196 |
{-Return next sorted element from the sort system}
|
197 |
|
198 |
procedure Reset;
|
199 |
{-Reset sorter before starting another sort}
|
200 |
|
201 |
property Count : LongInt
|
202 |
{-Return the number of elements in the sorter}
|
203 |
read FCount;
|
204 |
|
205 |
property Compare : TUntypedCompareFunc
|
206 |
{-Set or read the element comparison function}
|
207 |
read FCompare
|
208 |
write sorSetCompare;
|
209 |
|
210 |
property MergeName : TMergeNameFunc
|
211 |
{-Set or read the merge filename function}
|
212 |
read FMergeName
|
213 |
write FMergeName;
|
214 |
|
215 |
property RecLen : Cardinal
|
216 |
{-Return the size of each record}
|
217 |
read FRecLen;
|
218 |
end;
|
219 |
|
220 |
function OptimumHeapToUse(RecLen : Cardinal; NumRecs : LongInt) : LongInt;
|
221 |
{-Returns the optimum amount of heap space to sort NumRecs records
|
222 |
of RecLen bytes each. Less heap space causes merging; more heap
|
223 |
space is partially unused.}
|
224 |
|
225 |
function MinimumHeapToUse(RecLen : Cardinal) : LongInt;
|
226 |
{-Returns the absolute minimum heap that allows MergeSort to succeed}
|
227 |
|
228 |
function MergeInfo(MaxHeap : LongInt; RecLen : Cardinal;
|
229 |
NumRecs : LongInt) : TMergeInfo;
|
230 |
{-Predicts status and resource usage of a merge sort}
|
231 |
|
232 |
function DefaultMergeName(MergeNum : Integer) : string;
|
233 |
{-Default function used for returning merge file names}
|
234 |
|
235 |
procedure ArraySort(var A; RecLen, NumRecs : Cardinal;
|
236 |
Compare : TUntypedCompareFunc);
|
237 |
{-Sort a normal Delphi array (A) in place}
|
238 |
|
239 |
{======================================================================}
|
240 |
|
241 |
implementation
|
242 |
|
243 |
const
|
244 |
ecOutOfMemory = 8;
|
245 |
|
246 |
procedure RaiseError(Code : longint);
|
247 |
var
|
248 |
E : ESTSortError;
|
249 |
begin
|
250 |
if Code = ecOutOfMemory then
|
251 |
OutOfMemoryError
|
252 |
else begin
|
253 |
E := ESTSortError.CreateResTP(Code, 0);
|
254 |
E.ErrorCode := Code;
|
255 |
raise E;
|
256 |
end;
|
257 |
end;
|
258 |
|
259 |
function DefaultMergeName(MergeNum : Integer) : string;
|
260 |
begin
|
261 |
Result := 'SOR'+IntToStr(MergeNum)+'.TMP';
|
262 |
end;
|
263 |
|
264 |
function MergeInfo(MaxHeap : LongInt; RecLen : Cardinal;
|
265 |
NumRecs : LongInt) : TMergeInfo;
|
266 |
type
|
267 |
MergeFileSizeArray = array[1..(StMaxBlockSize div SizeOf(LongInt))] of LongInt;
|
268 |
var
|
269 |
MFileMerged, MOpenCount, MFileCount : Integer;
|
270 |
SizeBufSize, DiskSpace, OutputSpace, PeakDiskSpace : LongInt;
|
271 |
AllocRecs, RunCapacity, RecordsLeft, RecordsInFile : LongInt;
|
272 |
MFileSizeP : ^MergeFileSizeArray;
|
273 |
begin
|
274 |
{Set defaults for the result}
|
275 |
FillChar(Result, SizeOf(TMergeInfo), 0);
|
276 |
|
277 |
{Validate input parameters}
|
278 |
if (RecLen = 0) or (MaxHeap <= 0) or (NumRecs <= 0) then begin
|
279 |
Result.SortStatus := stscBadSize;
|
280 |
Exit;
|
281 |
end;
|
282 |
|
283 |
AllocRecs := MaxHeap div LongInt(RecLen);
|
284 |
if AllocRecs < MergeOrder+1 then begin
|
285 |
Result.SortStatus := stscBadSize;
|
286 |
Exit;
|
287 |
end;
|
288 |
|
289 |
RunCapacity := AllocRecs-2;
|
290 |
if RunCapacity < MinRecsPerRun then begin
|
291 |
Result.SortStatus := stscBadSize;
|
292 |
Exit;
|
293 |
end;
|
294 |
|
295 |
{Compute amount of memory used}
|
296 |
Result.HeapUsed := AllocRecs*LongInt(RecLen);
|
297 |
|
298 |
if RunCapacity >= NumRecs then
|
299 |
{All the records fit into memory}
|
300 |
Exit;
|
301 |
|
302 |
{Compute initial number of merge files and disk space}
|
303 |
MFileCount := NumRecs div (AllocRecs-2);
|
304 |
if NumRecs mod (AllocRecs-2) <> 0 then
|
305 |
inc(MFileCount);
|
306 |
{if MFileCount > MaxInt then begin }
|
307 |
{ Result.SortStatus := stscTooManyFiles;}
|
308 |
{ Exit; }
|
309 |
{end; }
|
310 |
DiskSpace := NumRecs*LongInt(RecLen);
|
311 |
|
312 |
{At least one merge phase required}
|
313 |
Result.MergePhases := 1;
|
314 |
|
315 |
if MFileCount <= MergeOrder then begin
|
316 |
{Only one merge phase, direct to user}
|
317 |
Result.MergeFiles := MFileCount;
|
318 |
Result.MergeHandles := MFileCount;
|
319 |
Result.MaxDiskSpace := DiskSpace;
|
320 |
Exit;
|
321 |
end;
|
322 |
|
323 |
{Compute total number of merge files and merge phases}
|
324 |
MFileMerged := 0;
|
325 |
while MFileCount-MFileMerged > MergeOrder do begin
|
326 |
inc(Result.MergePhases);
|
327 |
MOpenCount := 0;
|
328 |
while (MOpenCount < MergeOrder) and (MFileMerged < MFileCount) do begin
|
329 |
inc(MOpenCount);
|
330 |
inc(MFileMerged);
|
331 |
end;
|
332 |
inc(MFileCount);
|
333 |
end;
|
334 |
|
335 |
{Store the information we already know}
|
336 |
Result.MergeFiles := MFileCount;
|
337 |
Result.MergeHandles := MergeOrder+1; {MergeOrder input files, 1 output file}
|
338 |
|
339 |
{Determine whether the disk space analysis can proceed}
|
340 |
Result.MaxDiskSpace := -1;
|
341 |
if MFileCount > (StMaxBlockSize div SizeOf(LongInt)) then
|
342 |
Exit;
|
343 |
SizeBufSize := MFileCount*SizeOf(LongInt);
|
344 |
try
|
345 |
GetMem(MFileSizeP, SizeBufSize);
|
346 |
except
|
347 |
Exit;
|
348 |
end;
|
349 |
|
350 |
{Compute size of initial merge files}
|
351 |
RecordsLeft := NumRecs;
|
352 |
MFileCount := 0;
|
353 |
while RecordsLeft > 0 do begin
|
354 |
inc(MFileCount);
|
355 |
if RecordsLeft >= RunCapacity then
|
356 |
RecordsInFile := RunCapacity
|
357 |
else
|
358 |
RecordsInFile := RecordsLeft;
|
359 |
MFileSizeP^[MFileCount] := RecordsInFile*LongInt(RecLen);
|
360 |
dec(RecordsLeft, RecordsInFile);
|
361 |
end;
|
362 |
|
363 |
{Carry sizes forward to get disk space used}
|
364 |
PeakDiskSpace := DiskSpace;
|
365 |
MFileMerged := 0;
|
366 |
while MFileCount-MFileMerged > MergeOrder do begin
|
367 |
MOpenCount := 0;
|
368 |
OutputSpace := 0;
|
369 |
while (MOpenCount < MergeOrder) and (MFileMerged < MFileCount) do begin
|
370 |
inc(MOpenCount);
|
371 |
inc(MFileMerged);
|
372 |
inc(OutputSpace, MFileSizeP^[MFileMerged]);
|
373 |
end;
|
374 |
inc(MFileCount);
|
375 |
{Save size of output file}
|
376 |
MFileSizeP^[MFileCount] := OutputSpace;
|
377 |
{Output file and input files coexist temporarily}
|
378 |
inc(DiskSpace, OutputSpace);
|
379 |
{Store new peak disk space}
|
380 |
if DiskSpace > PeakDiskSpace then
|
381 |
PeakDiskSpace := DiskSpace;
|
382 |
{Account for deleting input files}
|
383 |
dec(DiskSpace, OutputSpace);
|
384 |
end;
|
385 |
Result.MaxDiskSpace := PeakDiskSpace;
|
386 |
|
387 |
FreeMem(MFileSizeP, SizeBufSize);
|
388 |
end;
|
389 |
|
390 |
function MinimumHeapToUse(RecLen : Cardinal) : LongInt;
|
391 |
var
|
392 |
HeapToUse : LongInt;
|
393 |
begin
|
394 |
HeapToUse := (MergeOrder+1)*RecLen;
|
395 |
Result := (MinRecsPerRun+2)*RecLen;
|
396 |
if Result < HeapToUse then
|
397 |
Result := HeapToUse;
|
398 |
end;
|
399 |
|
400 |
function OptimumHeapToUse(RecLen : Cardinal; NumRecs : LongInt) : LongInt;
|
401 |
begin
|
402 |
if (NumRecs < MergeOrder+1) then
|
403 |
NumRecs := MergeOrder+1;
|
404 |
Result := LongInt(RecLen)*(NumRecs+2);
|
405 |
end;
|
406 |
|
407 |
{----------------------------------------------------------------------}
|
408 |
|
409 |
constructor TStSorter.Create(MaxHeap : LongInt; RecLen : Cardinal);
|
410 |
begin
|
411 |
if (RecLen = 0) or (MaxHeap <= 0) then
|
412 |
RaiseError(stscBadSize);
|
413 |
|
414 |
FMergeName := DefaultMergeName;
|
415 |
FRecLen := RecLen;
|
416 |
|
417 |
{Allocate a sort work buffer using at most MaxHeap bytes}
|
418 |
sorAllocBuffer(MaxHeap);
|
419 |
|
420 |
{$IFDEF ThreadSafe}
|
421 |
Windows.InitializeCriticalSection(sorThreadSafe);
|
422 |
{$ENDIF}
|
423 |
end;
|
424 |
|
425 |
destructor TStSorter.Destroy;
|
426 |
begin
|
427 |
{$IFDEF ThreadSafe}
|
428 |
Windows.DeleteCriticalSection(sorThreadSafe);
|
429 |
{$ENDIF}
|
430 |
sorDeleteMergeFiles;
|
431 |
sorFreeBuffer;
|
432 |
end;
|
433 |
|
434 |
procedure TStSorter.EnterCS;
|
435 |
begin
|
436 |
{$IFDEF ThreadSafe}
|
437 |
EnterCriticalSection(sorThreadSafe);
|
438 |
{$ENDIF}
|
439 |
end;
|
440 |
|
441 |
function TStSorter.Get(var X) : Boolean;
|
442 |
var
|
443 |
NextIndex : Integer;
|
444 |
begin
|
445 |
{$IFDEF ThreadSafe}
|
446 |
EnterCS;
|
447 |
try
|
448 |
{$ENDIF}
|
449 |
Result := False;
|
450 |
|
451 |
if sorState <> 2 then begin
|
452 |
{First call to Get}
|
453 |
if sorRunCount > 0 then begin
|
454 |
{Still have elements to sort}
|
455 |
sorRunSort(0, sorRunCount-1);
|
456 |
if sorMergeFileCount > 0 then begin
|
457 |
{Already have other merge files}
|
458 |
sorStoreNewMergeFile;
|
459 |
sorPrimaryMerge;
|
460 |
sorOpenMergeFiles;
|
461 |
end else
|
462 |
{No merging necessary}
|
463 |
sorGetIndex := 0;
|
464 |
end else if FCount = 0 then
|
465 |
{No elements were sorted}
|
466 |
Exit;
|
467 |
|
468 |
sorState := 2;
|
469 |
end;
|
470 |
|
471 |
if sorMergeFileCount > 0 then begin
|
472 |
{Get next record from merge files}
|
473 |
NextIndex := sorGetNextElementIndex;
|
474 |
if NextIndex <> 0 then begin
|
475 |
{Return the element}
|
476 |
sorMoveElement(sorMergePtrs[NextIndex], @X);
|
477 |
{Get pointer to next element in the stream just used}
|
478 |
sorGetMergeElementPtr(NextIndex);
|
479 |
Result := True;
|
480 |
end;
|
481 |
end else if sorGetIndex < sorRunCount then begin
|
482 |
{Get next record from run buffer}
|
483 |
sorMoveElement(sorElementPtr(sorGetIndex), @X);
|
484 |
inc(sorGetIndex);
|
485 |
Result := True;
|
486 |
end;
|
487 |
{$IFDEF ThreadSafe}
|
488 |
finally
|
489 |
LeaveCS;
|
490 |
end;
|
491 |
{$ENDIF}
|
492 |
end;
|
493 |
|
494 |
procedure TStSorter.LeaveCS;
|
495 |
begin
|
496 |
{$IFDEF ThreadSafe}
|
497 |
LeaveCriticalSection(sorThreadSafe);
|
498 |
{$ENDIF}
|
499 |
end;
|
500 |
|
501 |
procedure TStSorter.Reset;
|
502 |
begin
|
503 |
{$IFDEF ThreadSafe}
|
504 |
EnterCS;
|
505 |
try
|
506 |
{$ENDIF}
|
507 |
sorDeleteMergeFiles;
|
508 |
FCount := 0;
|
509 |
sorState := 0;
|
510 |
sorRunCount := 0;
|
511 |
sorMergeFileCount := 0;
|
512 |
sorMergeFileMerged := 0;
|
513 |
sorMergeOpenCount := 0;
|
514 |
{$IFDEF ThreadSafe}
|
515 |
finally
|
516 |
LeaveCS;
|
517 |
end;
|
518 |
{$ENDIF}
|
519 |
end;
|
520 |
|
521 |
procedure TStSorter.Put(const X);
|
522 |
begin
|
523 |
{$IFDEF ThreadSafe}
|
524 |
EnterCS;
|
525 |
try
|
526 |
{$ENDIF}
|
527 |
if sorState = 2 then
|
528 |
{Can't Put after calling Get}
|
529 |
RaiseError(stscBadState);
|
530 |
|
531 |
sorState := 1;
|
532 |
|
533 |
if sorRunCount >= sorRunCapacity then begin
|
534 |
{Run buffer full; sort buffer and store to disk}
|
535 |
sorRunSort(0, sorRunCount-1);
|
536 |
sorStoreNewMergeFile;
|
537 |
sorRunCount := 0;
|
538 |
end;
|
539 |
|
540 |
{Store new element into run buffer}
|
541 |
sorMoveElement(@X, sorElementPtr(sorRunCount));
|
542 |
inc(sorRunCount);
|
543 |
inc(FCount);
|
544 |
{$IFDEF ThreadSafe}
|
545 |
finally
|
546 |
LeaveCS;
|
547 |
end;
|
548 |
{$ENDIF}
|
549 |
end;
|
550 |
|
551 |
procedure TStSorter.sorAllocBuffer(MaxHeap : LongInt);
|
552 |
{-Allocate a work buffer of records in at most MaxHeap bytes}
|
553 |
var
|
554 |
Status : Integer;
|
555 |
AllocRecs : LongInt;
|
556 |
begin
|
557 |
Status := stscBadSize;
|
558 |
repeat
|
559 |
AllocRecs := MaxHeap div LongInt(FRecLen);
|
560 |
if AllocRecs < MergeOrder+1 then
|
561 |
RaiseError(Status);
|
562 |
{$IFDEF Version6} {$WARN SYMBOL_PLATFORM OFF} {$ENDIF}
|
563 |
sorBuffer := GlobalAllocPtr(HeapAllocFlags, AllocRecs*LongInt(FRecLen));
|
564 |
{$IFDEF Version6} {$WARN SYMBOL_PLATFORM ON} {$ENDIF}
|
565 |
if sorBuffer = nil then begin
|
566 |
Status := ecOutOfMemory;
|
567 |
MaxHeap := MaxHeap div 2;
|
568 |
end else
|
569 |
break;
|
570 |
until False;
|
571 |
|
572 |
sorMergeBufSize := LongInt(FRecLen)*(AllocRecs div (MergeOrder+1));
|
573 |
|
574 |
sorRunCapacity := AllocRecs-2;
|
575 |
if sorRunCapacity < MinRecsPerRun then
|
576 |
RaiseError(Status);
|
577 |
|
578 |
sorPivotPtr := sorElementPtr(AllocRecs-1);
|
579 |
sorSwapPtr := sorElementPtr(AllocRecs-2);
|
580 |
end;
|
581 |
|
582 |
procedure TStSorter.sorCreateNewMergeFile(var Handle : Integer);
|
583 |
{-Create another merge file and return its handle}
|
584 |
begin
|
585 |
if sorMergeFileCount = MaxInt then
|
586 |
{Too many merge files}
|
587 |
RaiseError(stscTooManyFiles);
|
588 |
|
589 |
{Create new merge file}
|
590 |
inc(sorMergeFileCount);
|
591 |
Handle := FileCreate(FMergeName(sorMergeFileCount));
|
592 |
if Handle < 0 then begin
|
593 |
dec(sorMergeFileCount);
|
594 |
RaiseError(stscFileCreate);
|
595 |
end;
|
596 |
end;
|
597 |
|
598 |
procedure TStSorter.sorDeleteMergeFiles;
|
599 |
{-Delete open and already-closed merge files}
|
600 |
var
|
601 |
I : Integer;
|
602 |
begin
|
603 |
for I := 1 to sorMergeOpenCount do begin
|
604 |
FileClose(sorMergeFiles[I]);
|
605 |
SysUtils.DeleteFile(FMergeName(sorMergeFileNumber[I]));
|
606 |
end;
|
607 |
|
608 |
for I := sorMergeFileMerged+1 to sorMergeFileCount do
|
609 |
SysUtils.DeleteFile(FMergeName(I));
|
610 |
end;
|
611 |
|
612 |
function TStSorter.sorElementPtr(Index : LongInt) : Pointer;
|
613 |
{-Return a pointer to the given element in the sort buffer}
|
614 |
begin
|
615 |
Result := PAnsiChar(sorBuffer)+Index*LongInt(FRecLen);
|
616 |
end;
|
617 |
|
618 |
procedure TStSorter.sorFlushOutBuffer;
|
619 |
{-Write the merge output buffer to disk}
|
620 |
var
|
621 |
BytesWritten : LongInt;
|
622 |
begin
|
623 |
if sorOutBytesUsed <> 0 then begin
|
624 |
BytesWritten := FileWrite(sorOutFile, sorOutPtr^, sorOutBytesUsed);
|
625 |
if BytesWritten <> sorOutBytesUsed then
|
626 |
RaiseError(stscFileWrite);
|
627 |
end;
|
628 |
end;
|
629 |
|
630 |
procedure TStSorter.sorFreeBuffer;
|
631 |
begin
|
632 |
GlobalFreePtr(sorBuffer);
|
633 |
end;
|
634 |
|
635 |
procedure TStSorter.sorGetMergeElementPtr(M : Integer);
|
636 |
{-Update head pointer in input buffer of specified open merge file}
|
637 |
var
|
638 |
BytesRead : LongInt;
|
639 |
begin
|
640 |
if sorMergeBytesUsed[M] >= sorMergeBytesLoaded[M] then begin
|
641 |
{Try to load new data into buffer}
|
642 |
BytesRead := FileRead(sorMergeFiles[M], sorMergeBases[M]^, sorMergeBufSize);
|
643 |
if BytesRead < 0 then
|
644 |
{Error reading file}
|
645 |
RaiseError(stscFileRead);
|
646 |
if BytesRead < LongInt(FRecLen) then begin
|
647 |
{End of file. Close and delete it}
|
648 |
FileClose(sorMergeFiles[M]);
|
649 |
SysUtils.DeleteFile(FMergeName(sorMergeFileNumber[M]));
|
650 |
{Remove file from merge list}
|
651 |
if M <> sorMergeOpenCount then begin
|
652 |
sorMergeFileNumber[M] := sorMergeFileNumber[sorMergeOpenCount];
|
653 |
sorMergeFiles[M] := sorMergeFiles[sorMergeOpenCount];
|
654 |
sorMergePtrs[M] := sorMergePtrs[sorMergeOpenCount];
|
655 |
sorMergeBytesLoaded[M] := sorMergeBytesLoaded[sorMergeOpenCount];
|
656 |
sorMergeBytesUsed[M] := sorMergeBytesUsed[sorMergeOpenCount];
|
657 |
sorMergeBases[M] := sorMergeBases[sorMergeOpenCount];
|
658 |
end;
|
659 |
dec(sorMergeOpenCount);
|
660 |
Exit;
|
661 |
end;
|
662 |
sorMergeBytesLoaded[M] := BytesRead;
|
663 |
sorMergeBytesUsed[M] := 0;
|
664 |
end;
|
665 |
|
666 |
sorMergePtrs[M] := PAnsiChar(sorMergeBases[M])+sorMergeBytesUsed[M];
|
667 |
inc(sorMergeBytesUsed[M], FRecLen);
|
668 |
end;
|
669 |
|
670 |
function TStSorter.sorGetNextElementIndex : Integer;
|
671 |
{-Return index into open merge file of next smallest element}
|
672 |
var
|
673 |
M : Integer;
|
674 |
MinElPtr : Pointer;
|
675 |
begin
|
676 |
if sorMergeOpenCount = 0 then begin
|
677 |
{All merge streams are empty}
|
678 |
Result := 0;
|
679 |
Exit;
|
680 |
end;
|
681 |
|
682 |
{Assume first element is the least}
|
683 |
MinElPtr := sorMergePtrs[1];
|
684 |
Result := 1;
|
685 |
|
686 |
{Scan the other elements}
|
687 |
for M := 2 to sorMergeOpenCount do
|
688 |
if FCompare(sorMergePtrs[M]^, MinElPtr^) < 0 then begin
|
689 |
Result := M;
|
690 |
MinElPtr := sorMergePtrs[M];
|
691 |
end;
|
692 |
end;
|
693 |
|
694 |
procedure TStSorter.sorMergeFileGroup;
|
695 |
{-Merge a group of input files into one output file}
|
696 |
var
|
697 |
NextIndex : Integer;
|
698 |
begin
|
699 |
sorOutBytesUsed := 0;
|
700 |
repeat
|
701 |
{Find index of minimum element}
|
702 |
NextIndex := sorGetNextElementIndex;
|
703 |
if NextIndex = 0 then
|
704 |
break
|
705 |
else begin
|
706 |
{Copy element to output}
|
707 |
sorStoreElement(sorMergePtrs[NextIndex]);
|
708 |
{Get the next element from its merge stream}
|
709 |
sorGetMergeElementPtr(NextIndex);
|
710 |
end;
|
711 |
until False;
|
712 |
|
713 |
{Flush and close the output file}
|
714 |
sorFlushOutBuffer;
|
715 |
FileClose(sorOutFile);
|
716 |
end;
|
717 |
|
718 |
procedure TStSorter.sorMoveElement(Src, Dest : Pointer); assembler;
|
719 |
{-Copy one record to another location, non-overlapping}
|
720 |
register;
|
721 |
asm
|
722 |
{eax = Self, edx = Src, ecx = Dest}
|
723 |
push esi
|
724 |
mov esi,Src
|
725 |
mov edx,edi
|
726 |
mov edi,Dest
|
727 |
mov ecx,TStSorter([eax]).FRecLen
|
728 |
mov eax,ecx
|
729 |
shr ecx,2
|
730 |
rep movsd
|
731 |
mov ecx,eax
|
732 |
and ecx,3
|
733 |
rep movsb
|
734 |
mov edi,edx
|
735 |
pop esi
|
736 |
end;
|
737 |
|
738 |
procedure TStSorter.sorOpenMergeFiles;
|
739 |
{-Open a group of up to MergeOrder input files}
|
740 |
begin
|
741 |
sorMergeOpenCount := 0;
|
742 |
while (sorMergeOpenCount < MergeOrder) and
|
743 |
(sorMergeFileMerged < sorMergeFileCount) do begin
|
744 |
inc(sorMergeOpenCount);
|
745 |
{Open associated merge file}
|
746 |
inc(sorMergeFileMerged);
|
747 |
sorMergeFiles[sorMergeOpenCount] :=
|
748 |
FileOpen(FMergeName(sorMergeFileMerged), fmOpenRead);
|
749 |
if sorMergeFiles[sorMergeOpenCount] < 0 then begin
|
750 |
dec(sorMergeFileMerged);
|
751 |
dec(sorMergeOpenCount);
|
752 |
RaiseError(stscFileOpen);
|
753 |
end;
|
754 |
{File number of merge file}
|
755 |
sorMergeFileNumber[sorMergeOpenCount] := sorMergeFileMerged;
|
756 |
{Selector for merge file}
|
757 |
sorMergePtrs[sorMergeOpenCount] := PAnsiChar(sorBuffer)+
|
758 |
(sorMergeOpenCount-1)*sorMergeBufSize;
|
759 |
{Number of bytes currently in merge buffer}
|
760 |
sorMergeBytesLoaded[sorMergeOpenCount] := 0;
|
761 |
{Number of bytes used in merge buffer}
|
762 |
sorMergeBytesUsed[sorMergeOpenCount] := 0;
|
763 |
{Save the merge pointer}
|
764 |
sorMergeBases[sorMergeOpenCount] := sorMergePtrs[sorMergeOpenCount];
|
765 |
{Get the first element}
|
766 |
sorGetMergeElementPtr(sorMergeOpenCount);
|
767 |
end;
|
768 |
end;
|
769 |
|
770 |
procedure TStSorter.sorPrimaryMerge;
|
771 |
{-Merge until there are no more than MergeOrder merge files left}
|
772 |
begin
|
773 |
sorOutPtr := PAnsiChar(sorBuffer)+MergeOrder*sorMergeBufSize;
|
774 |
while sorMergeFileCount-sorMergeFileMerged > MergeOrder do begin
|
775 |
{Open next group of MergeOrder files}
|
776 |
sorOpenMergeFiles;
|
777 |
{Create new output file}
|
778 |
sorCreateNewMergeFile(sorOutFile);
|
779 |
{Merge these files into the output}
|
780 |
sorMergeFileGroup;
|
781 |
end;
|
782 |
end;
|
783 |
|
784 |
procedure TStSorter.sorRunSort(L, R : LongInt);
|
785 |
{-Sort one run buffer full of records in memory using non-recursive QuickSort}
|
786 |
const
|
787 |
StackSize = 32;
|
788 |
type
|
789 |
Stack = array[0..StackSize-1] of LongInt;
|
790 |
var
|
791 |
Pl : LongInt; {Left edge within partition}
|
792 |
Pr : LongInt; {Right edge within partition}
|
793 |
Pm : LongInt; {Mid-point of partition}
|
794 |
PartitionLen : LongInt; {Size of current partition}
|
795 |
StackP : Integer; {Stack pointer}
|
796 |
Lstack : Stack; {Pending partitions, left edge}
|
797 |
Rstack : Stack; {Pending partitions, right edge}
|
798 |
begin
|
799 |
{Make sure there's a compare function}
|
800 |
if @FCompare = nil then
|
801 |
RaiseError(stscNoCompare);
|
802 |
|
803 |
{Initialize the stack}
|
804 |
StackP := 0;
|
805 |
Lstack[0] := L;
|
806 |
Rstack[0] := R;
|
807 |
|
808 |
{Repeatedly take top partition from stack}
|
809 |
repeat
|
810 |
|
811 |
{Pop the stack}
|
812 |
L := Lstack[StackP];
|
813 |
R := Rstack[StackP];
|
814 |
Dec(StackP);
|
815 |
|
816 |
{Sort current partition}
|
817 |
repeat
|
818 |
Pl := L;
|
819 |
Pr := R;
|
820 |
PartitionLen := Pr-Pl+1;
|
821 |
|
822 |
{$IFDEF MidPoint}
|
823 |
Pm := Pl+(PartitionLen shr 1);
|
824 |
{$ENDIF}
|
825 |
|
826 |
{$IFDEF Random}
|
827 |
Pm := Pl+Random(PartitionLen);
|
828 |
{$ENDIF}
|
829 |
|
830 |
{$IFDEF Median}
|
831 |
Pm := Pl+(PartitionLen shr 1);
|
832 |
if PartitionLen >= MedianThreshold then begin
|
833 |
{Sort elements Pl, Pm, Pr}
|
834 |
if FCompare(sorElementPtr(Pm)^, sorElementPtr(Pl)^) < 0 then
|
835 |
sorSwapElements(Pm, Pl);
|
836 |
if FCompare(sorElementPtr(Pr)^, sorElementPtr(Pl)^) < 0 then
|
837 |
sorSwapElements(Pr, Pl);
|
838 |
if FCompare(sorElementPtr(Pr)^, sorElementPtr(Pm)^) < 0 then
|
839 |
sorSwapElements(Pr, Pm);
|
840 |
|
841 |
{Exchange Pm with Pr-1 but use Pm's value as the pivot}
|
842 |
sorSwapElements(Pm, Pr-1);
|
843 |
Pm := Pr-1;
|
844 |
|
845 |
{Reduce range of swapping}
|
846 |
inc(Pl);
|
847 |
dec(Pr, 2);
|
848 |
end;
|
849 |
{$ENDIF}
|
850 |
|
851 |
{Save the pivot element}
|
852 |
sorMoveElement(sorElementPtr(Pm), sorPivotPtr);
|
853 |
|
854 |
{Swap items in sort order around the pivot}
|
855 |
repeat
|
856 |
while FCompare(sorElementPtr(Pl)^, sorPivotPtr^) < 0 do
|
857 |
Inc(Pl);
|
858 |
while FCompare(sorPivotPtr^, sorElementPtr(Pr)^) < 0 do
|
859 |
Dec(Pr);
|
860 |
|
861 |
if Pl = Pr then begin
|
862 |
{Reached the pivot}
|
863 |
Inc(Pl);
|
864 |
Dec(Pr);
|
865 |
end else if Pl < Pr then begin
|
866 |
{Swap elements around the pivot}
|
867 |
sorSwapElements(Pl, Pr);
|
868 |
Inc(Pl);
|
869 |
Dec(Pr);
|
870 |
end;
|
871 |
until Pl > Pr;
|
872 |
|
873 |
{Decide which partition to sort next}
|
874 |
if (Pr-L) < (R-Pl) then begin
|
875 |
{Left partition is bigger}
|
876 |
if Pl < R then begin
|
877 |
{Stack the request for sorting right partition}
|
878 |
Inc(StackP);
|
879 |
Lstack[StackP] := Pl;
|
880 |
Rstack[StackP] := R;
|
881 |
end;
|
882 |
{Continue sorting left partition}
|
883 |
R := Pr;
|
884 |
end else begin
|
885 |
{Right partition is bigger}
|
886 |
if L < Pr then begin
|
887 |
{Stack the request for sorting left partition}
|
888 |
Inc(StackP);
|
889 |
Lstack[StackP] := L;
|
890 |
Rstack[StackP] := Pr;
|
891 |
end;
|
892 |
{Continue sorting right partition}
|
893 |
L := Pl;
|
894 |
end;
|
895 |
until L >= R;
|
896 |
until StackP < 0;
|
897 |
end;
|
898 |
|
899 |
procedure TStSorter.sorSetCompare(Comp : TUntypedCompareFunc);
|
900 |
{-Set the compare function, with error checking}
|
901 |
begin
|
902 |
if ((FCount <> 0) or (@Comp = nil)) and (@Comp <> @FCompare) then
|
903 |
RaiseError(stscBadCompare);
|
904 |
FCompare := Comp;
|
905 |
end;
|
906 |
|
907 |
procedure TStSorter.sorStoreElement(Src : Pointer);
|
908 |
{-Store element in the merge output buffer}
|
909 |
begin
|
910 |
if sorOutBytesUsed >= sorMergeBufSize then begin
|
911 |
sorFlushOutBuffer;
|
912 |
sorOutBytesUsed := 0;
|
913 |
end;
|
914 |
sorMoveElement(Src, PAnsiChar(sorOutPtr)+sorOutBytesUsed);
|
915 |
inc(sorOutBytesUsed, FRecLen);
|
916 |
end;
|
917 |
|
918 |
procedure TStSorter.sorStoreNewMergeFile;
|
919 |
{-Create new merge file, write run buffer to it, close file}
|
920 |
var
|
921 |
BytesToWrite, BytesWritten : Integer;
|
922 |
begin
|
923 |
sorCreateNewMergeFile(sorOutFile);
|
924 |
try
|
925 |
BytesToWrite := sorRunCount*LongInt(FRecLen);
|
926 |
BytesWritten := FileWrite(sorOutFile, sorBuffer^, BytesToWrite);
|
927 |
if BytesWritten <> BytesToWrite then
|
928 |
RaiseError(stscFileWrite);
|
929 |
finally
|
930 |
{Close merge file}
|
931 |
FileClose(sorOutFile);
|
932 |
end;
|
933 |
end;
|
934 |
|
935 |
procedure TStSorter.sorSwapElements(L, R : LongInt);
|
936 |
{-Swap elements with indexes L and R}
|
937 |
var
|
938 |
LPtr : Pointer;
|
939 |
RPtr : Pointer;
|
940 |
begin
|
941 |
LPtr := sorElementPtr(L);
|
942 |
RPtr := sorElementPtr(R);
|
943 |
sorMoveElement(LPtr, sorSwapPtr);
|
944 |
sorMoveElement(RPtr, LPtr);
|
945 |
sorMoveElement(sorSwapPtr, RPtr);
|
946 |
end;
|
947 |
|
948 |
procedure ArraySort(var A; RecLen, NumRecs : Cardinal;
|
949 |
Compare : TUntypedCompareFunc);
|
950 |
const
|
951 |
StackSize = 32;
|
952 |
type
|
953 |
Stack = array[0..StackSize-1] of LongInt;
|
954 |
var
|
955 |
Pl, Pr, Pm, L, R : LongInt;
|
956 |
ArraySize, PartitionLen : LongInt;
|
957 |
PivotPtr : Pointer;
|
958 |
SwapPtr : Pointer;
|
959 |
StackP : Integer;
|
960 |
Lstack, Rstack : Stack;
|
961 |
|
962 |
function ElementPtr(Index : Cardinal) : Pointer;
|
963 |
begin
|
964 |
Result := PAnsiChar(@A)+Index*RecLen;
|
965 |
end;
|
966 |
|
967 |
procedure SwapElements(L, R : LongInt);
|
968 |
var
|
969 |
LPtr : Pointer;
|
970 |
RPtr : Pointer;
|
971 |
begin
|
972 |
LPtr := ElementPtr(L);
|
973 |
RPtr := ElementPtr(R);
|
974 |
Move(LPtr^, SwapPtr^, RecLen);
|
975 |
Move(RPtr^, LPtr^, RecLen);
|
976 |
Move(SwapPtr^, RPtr^, RecLen);
|
977 |
end;
|
978 |
|
979 |
begin
|
980 |
{Make sure there's a compare function}
|
981 |
if @Compare = nil then
|
982 |
RaiseError(stscNoCompare);
|
983 |
|
984 |
{Make sure the array size is reasonable}
|
985 |
ArraySize := LongInt(RecLen)*LongInt(NumRecs);
|
986 |
if (ArraySize = 0) {or (ArraySize > MaxBlockSize)} then
|
987 |
RaiseError(stscBadSize);
|
988 |
|
989 |
{Get pivot and swap elements}
|
990 |
GetMem(PivotPtr, RecLen);
|
991 |
try
|
992 |
GetMem(SwapPtr, RecLen);
|
993 |
try
|
994 |
{Initialize the stack}
|
995 |
StackP := 0;
|
996 |
Lstack[0] := 0;
|
997 |
Rstack[0] := NumRecs-1;
|
998 |
|
999 |
{Repeatedly take top partition from stack}
|
1000 |
repeat
|
1001 |
|
1002 |
{Pop the stack}
|
1003 |
L := Lstack[StackP];
|
1004 |
R := Rstack[StackP];
|
1005 |
Dec(StackP);
|
1006 |
|
1007 |
{Sort current partition}
|
1008 |
repeat
|
1009 |
Pl := L;
|
1010 |
Pr := R;
|
1011 |
PartitionLen := Pr-Pl+1;
|
1012 |
|
1013 |
{$IFDEF MidPoint}
|
1014 |
Pm := Pl+(PartitionLen shr 1);
|
1015 |
{$ENDIF}
|
1016 |
|
1017 |
{$IFDEF Random}
|
1018 |
Pm := Pl+Random(PartitionLen);
|
1019 |
{$ENDIF}
|
1020 |
|
1021 |
{$IFDEF Median}
|
1022 |
Pm := Pl+(PartitionLen shr 1);
|
1023 |
if PartitionLen >= MedianThreshold then begin
|
1024 |
{Sort elements Pl, Pm, Pr}
|
1025 |
if Compare(ElementPtr(Pm)^, ElementPtr(Pl)^) < 0 then
|
1026 |
SwapElements(Pm, Pl);
|
1027 |
if Compare(ElementPtr(Pr)^, ElementPtr(Pl)^) < 0 then
|
1028 |
SwapElements(Pr, Pl);
|
1029 |
if Compare(ElementPtr(Pr)^, ElementPtr(Pm)^) < 0 then
|
1030 |
SwapElements(Pr, Pm);
|
1031 |
|
1032 |
{Exchange Pm with Pr-1 but use Pm's value as the pivot}
|
1033 |
SwapElements(Pm, Pr-1);
|
1034 |
Pm := Pr-1;
|
1035 |
|
1036 |
{Reduce range of swapping}
|
1037 |
inc(Pl);
|
1038 |
dec(Pr, 2);
|
1039 |
end;
|
1040 |
{$ENDIF}
|
1041 |
|
1042 |
{Save the pivot element}
|
1043 |
Move(ElementPtr(Pm)^, PivotPtr^, RecLen);
|
1044 |
|
1045 |
{Swap items in sort order around the pivot}
|
1046 |
repeat
|
1047 |
while Compare(ElementPtr(Pl)^, PivotPtr^) < 0 do
|
1048 |
Inc(Pl);
|
1049 |
while Compare(PivotPtr^, ElementPtr(Pr)^) < 0 do
|
1050 |
Dec(Pr);
|
1051 |
|
1052 |
if Pl = Pr then begin
|
1053 |
{Reached the pivot}
|
1054 |
Inc(Pl);
|
1055 |
Dec(Pr);
|
1056 |
end else if Pl < Pr then begin
|
1057 |
{Swap elements around the pivot}
|
1058 |
SwapElements(Pl, Pr);
|
1059 |
Inc(Pl);
|
1060 |
Dec(Pr);
|
1061 |
end;
|
1062 |
until Pl > Pr;
|
1063 |
|
1064 |
{Decide which partition to sort next}
|
1065 |
if (Pr-L) < (R-Pl) then begin
|
1066 |
{Left partition is bigger}
|
1067 |
if Pl < R then begin
|
1068 |
{Stack the request for sorting right partition}
|
1069 |
Inc(StackP);
|
1070 |
Lstack[StackP] := Pl;
|
1071 |
Rstack[StackP] := R;
|
1072 |
end;
|
1073 |
{Continue sorting left partition}
|
1074 |
R := Pr;
|
1075 |
end else begin
|
1076 |
{Right partition is bigger}
|
1077 |
if L < Pr then begin
|
1078 |
{Stack the request for sorting left partition}
|
1079 |
Inc(StackP);
|
1080 |
Lstack[StackP] := L;
|
1081 |
Rstack[StackP] := Pr;
|
1082 |
end;
|
1083 |
{Continue sorting right partition}
|
1084 |
L := Pl;
|
1085 |
end;
|
1086 |
until L >= R;
|
1087 |
until StackP < 0;
|
1088 |
|
1089 |
finally
|
1090 |
FreeMem(SwapPtr, RecLen);
|
1091 |
end;
|
1092 |
finally
|
1093 |
FreeMem(PivotPtr, RecLen);
|
1094 |
end;
|
1095 |
end;
|
1096 |
|
1097 |
|
1098 |
end.
|