External sort: Difference between revisions

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|Nim}}==

{{trans|Phix}}

 

 

 

 

for filename in filenames:

 

{{out}}

=={{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>

 

This particular example uses the DOS &nbsp; '''SORT''' &nbsp; and &nbsp; '''ERASE''' &nbsp; commands.

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. */

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

srt: procedure expose sWork; parse arg #

 

=={{header|Wren}}==

{{libheader|Wren-str}}

A bit simpler than the Go version as we use fixed length integers which (together with a following space) can be sorted as strings.

import "random" for Random

 

var MinHeapNode = Struct.create("MinHeapNode", ["element", "index"])

var fileName = "es%(i)"

File.delete(fileName)

 

{{out}}