in reply to [OT] A measure of 'sortedness'?

Q: How to sort lots of data.
A: Using mergesort.

Let's say we have a dataset amounting to D, and M is the size that can be comfortably sorted in-memory. Now the first step suggests itself: divide data up in n = D / M chunks, sort each one separately. This much is already on the blueprints, I'd imagine.

The second step is to merge the n stripes. Merge pass is a streaming operation, it does not require any storage per se. Though for efficient handling, fill buffers are practical.

N-way merge may be accomplished via network of two-way merges. E.g. 4-way merge might be defined as follows: 

merge2(merge2(,), merge2(,))

[download]
Those merge junctions assemble like drainage pipes. An n-way merge requires n-1 junctions, and 2n-1 fill buffers for I/O. The second pass will read and write all of the data records for the second time.

As for the implementation: AVX2 intrinsics should prove handy with vectors of 64bit integers. Fill buffers in megabytes might be needed with mechanical storage.

Replies are listed 'Best First'.
Re^2: [OT] A measure of 'sortedness'?
by BrowserUk (Patriarch) on Mar 20, 2015 at 17:44 UTC
    Q: How to sort lots of data. A: Using mergesort.

    Ooh! Why didn't I think of that. Erm . Let me re-phrase: What makes you think I haven't already considered that?

    That is the traditional way isn't it. (Surprised its taken you 3 days to look that up.) So what's wrong with the traditional way?

    To find out, generate yourself a 100GB file of random 64-bit ints (about 15 minutes work with a one-liner) and then use your local system sort utility to sort it. Then come back to me when its finished, and we'll discuss it further.

    See you in 3 or 4 days!

    With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    "Science is about questioning the status quo. Questioning authority". I'm with torvalds on this
    In the absence of evidence, opinion is indistinguishable from prejudice. Agile (and TDD) debunked
[reply]

      If you sort the chunks while generating, then apply the n-way merge as described—that full procedure results in a 100GB write, plus another 100GB of reads and 100 GB of writes. In total, 300GB of streaming (external memory access).

      You are searching for an algorithm that does better, or claim to have found one?

[reply]
        If you sort the chunks while generating,

        That presupposes that I'm generating the files.

        You are searching for an algorithm that does better

        I'm writing a utility to sort (much) larger-than-memory files of fixed-length records.

        I already have a working version -- actually several, each an improvement on the previous -- but they are pretty slow. Infinitely faster than my system sort utility, but still significant room for improvement.

        or claim to have found one?

        It is not hard to beat your local system sort utility for this purpose.

        To understand why, you really need to do as I suggested, generate a large, fixed-length record binary file, and try them for yourself.

        With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
        Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
        "Science is about questioning the status quo. Questioning authority". I'm with torvalds on this
        In the absence of evidence, opinion is indistinguishable from prejudice. Agile (and TDD) debunked
[reply]

In Section Seekers of Perl Wisdom