> (Well you could tie an AoA to a file representing a table. Sorting that array would go without much RAM but mean constant overhead with each access. This is certainly worth a shot, but as I said DBs have this already optimized.)

I don't think this will work because of the way merge sort is implemented in Perl

It is first comparing all pairs in a breadth first search, which would mean far too many disk operations and no sensible caching option

  DB<7> sort { print "$a,$b  |"; $a <=> $b } reverse 1..16
16,15  |14,13  |12,11  |10,9  |8,7  |6,5  |4,3  |2,1  |15,13  |15,14  
+|11,9  |11,10  |13,9  |13,10  |13,11  |13,12  \
|7,5  |7,6  |3,1  |3,2  |5,1  |5,2  |5,3  |5,4  |9,1  |9,2  |9,3  |9,4
+  |9,5  |9,6  |9,7  |9,8  |
  DB<8>

[download]

explained 

16,15  |14,13     |12,11  |10,9     |8,7  |6,5    |4,3  |2,1  |       
+      # sort pairs
15,13  |15,14     |11,9  |11,10                                       
+      # sort 1st and 2nd 4-tuple
|13,9  |13,10    |13,11  |13,12                                       
+      # sort 1st 8 tuple
                                    |7,5  |7,6    |3,1  |3,2          
+      # sort 3rd and 4th 4-tuple
                                    |5,1  |5,2  |5,3  |5,4            
+      # sort 2nd 8tuple

      |9,1  |9,2  |9,3  |9,4  |9,5  |9,6  |9,7  |9,8  |               
+      # sort 16 tuple

[download]

A caching/memoizing of data read from disk would be far more efficient if the chunks were strictly chosen depth first.

FWIW WP lists some divide-and-conquer approaches for merge-sort

https://en.wikipedia.org/wiki/Mergesort#Parallel_merge_sort

Cheers Rolf
(addicted to the Perl Programming Language :)
Wikisyntax for the Monastery

In reply to Re^4: efficient perl code to count, rank (merge sort) by LanX
in thread efficient perl code to count, rank by Perl_Noob2021

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.