Krambambuli,
Before answering your question, keep in mind I already allowed for both lists to fit in memory as a given. In reality, if you had a really large list you probably wouldn't be going through these contortions - you would probably sort on disk.

Here are a few links to help your main question

• Merge Algorithm (Combining Sorted Lists) (iterator version)
• Iterator article I wrote for perl.com
• How A Function Becomes Higher Order
• Higher Order Perl (I recommend you support the author and by the dead tree edition)

I guess your question boils down to: How can you do this with even less than 2N + M? blokhead has shown a solution that uses no memory but takes (N*M)^2 to run. TO give you a specific answer, one would need a specific problem. As I demonstrated in How many words does it take?, the trick to solving really hard problems in the general case (NP complete) is to exploit the details of the specific case (effectively turned into O(1)).

---

---

• Are you posting in the right place? Check out Where do I post X? to know for sure.
• Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:

  <code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>

• Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
• Want more info? How to link or How to display code and escape characters are good places to start.