External sort: Difference between revisions

{{Sorting Algorithm}}

{{draft task|Sorting Algorithms}}

 

A "half chunk" of integers at a time is read to each of two buffer lists covering different sections of the file range being partitioned. Only those integers needing to be swapped are written back to the file and each list is replaced as it's used up. When the converging sections eventually overlap, a single list is used instead which is updated in parallel with the file to ensure that the partitioning repeat stops in the right place. Partitions less than a "chunk" in length are sorted in memory with a heap sort. (The Foundation framework has a built-in NSMutableArray sort which is faster than a vanilla heap sort — even with the necessary derivation of NSMutableArrays from the lists and lists from the sorted arrays — but I don't know how well this fits the task's "low memory" conceit.)

 

Quicksort algorithm: S.A.R. (Tony) Hoare, 1960.

Optimisations by Robert Sedgewick and others at various times.

 

set theFile to (path to desktop as text) & "Test.dat"

 

=={{header|C++}}==

All sorted streams are merged in this way out to an external output file ''merged.txt''.

/* ExternalSort.cpp */

 

 

/* inputfile integers -- one per line for simplicity */

 

{{out}}

 

A small test file consisting of random integers has been generated and sorted to demonstrate that the approach works.

 

import (

check(err)

}

 

{{out}}

</pre>

 

Untested on a memory mapped file.

NB. Apply an in-place sorting algorithm to a memory mapped file

NB. in-place sort is translation of in-place python quicksort.

i. 0 0 NB. verbs return the final noun

)

 

Demonstration the sorting works:

 

=={{header|Julia}}==

 

arr = Mmap.mmap(intfile, Vector{Int64}, (div(stat(intfile).size, 8))) # Int64 is 8 bytes

 

sort!(arr)

 

=={{header|Perl}}==

Simulate task by reading from 'DATA' handle and using tiny record limit. As written, works for any numeric input, but could define any kind of customized sorting.

use warnings;

 

654

789

{{out}}

<pre>123

=={{header|Phix}}==

Slight variation on [[Stream_Merge#Phix|Stream_Merge]]

{{out}}

<pre>

=={{header|Python}}==

A technique demonstrated with a short string character data.

#! /usr/bin/python3

 

example = main

example()

 

=={{header|Raku}}==

(formerly Perl 6)

Borrowing from [http://rosettacode.org/wiki/Stream_Merge Stream_Merge] here. Temporary files are automatically deleted when program is done, so no explicit clean-up required.

 

sub merge_streams ( @streams ) {

@files.push: store(@chunk) if @chunk;

 

{{out}}

<pre>-11 -9 -2 0 2 3 4 15 32 34 42 43 45 45 55 64 66 76 78 87 92 123</pre>

<br>The sort work files are then sorted with an external sort, and then merged into one big file.

 

parse arg FID n lim seed . /*obtain optional arguments from the CL*/

if FID=='' | FID=="," then FID= 'SORT_EXT.OUT' /*name of the output (sorted) file. */

if datatype(seed, 'W') then call random ,,seed /*Numeric? Then use it as a rand seed.*/

sWork = 'SORTWORK.' /*the filename of the SORTWORK files.*/

call srt # /*sort records in all SORTWORK files.*/

call mrg /*merge records in the SORTWORK files.*/

/*──────────────────────────────────────────────────────────────────────────────────────*/

@.= copies('ff'x, 1e5) /*no value should be larger than this. */

call lineout FID, , 1 /*position the output file at rec # 1. */

end /*j*/ /*but initially just 1 record per file.*/

if z==0 then leave /*Any more records? No, close file. */

call lineout FID, @.z /*write the value to the output file. */

call rdr z /*re-populate a value from the # file. */

end /*forever*/ /*keep reading/merging until exhausted.*/

call lineout FID /*close the output file (just in case).*/

return

/*──────────────────────────────────────────────────────────────────────────────────────*/

# = 0 /*number of SORTWORK.nnn files so far*/

/*──────────────────────────────────────────────────────────────────────────────────────*/

/*──────────────────────────────────────────────────────────────────────────────────────*/

srt: procedure expose sWork; parse arg #