title: Improvements for a Map merge function
body: <p>I'm writing a function to merge two Map's together.  This is what I have so far:</p>
  
  <pre><code>def merge[K, V1, V2, V3](left: Map[K, V1], right: Map[K, V2])
      (fn: (Option[V1], Option[V2]) =&gt; V3): Map[K, V3] = {
    val r = (left.keySet ++ right.keySet) map {
      key =&gt;
        (key -&gt; fn(left.get(key), right.get(key)))
    }
    r.toMap
  }
  </code></pre>
  
  <p>The function itself works.  You use the function as so:</p>
  
  <pre><code>val m1 = Map(1 -&gt; "one", 3 -&gt; "three", 5 -&gt; "five")
  val m2 = Map(1 -&gt; "I", 5 -&gt; "V", 10 -&gt; "X")
  merge(m1, m2) { (_, _) } 
  // returns: 
  // Map(1 -&gt; (Some(one),Some(I)), 
  //     3 -&gt; (Some(three),None), 
  //     5 -&gt; (Some(five),Some(V)), 
  //     10 -&gt; (None,Some(X)))
  </code></pre>
  
  <p>I have two questions:</p>
  
  <ol>
  <li>I'm worried about the <strike>performance</strike> computational complexity of the <code>.get</code> and <code>.toMap</code> calls.  Can anyone improve the implementation?</li>
  <li>I'd like the default function to make a pair of the values (<code>{ (_, _) }</code>).  I can't quite get the syntax to do so properly.</li>
  </ol>
  
  <p><em><strong>Edit:</em></strong>
  While I originally said performance, I meant computational complexity.  <strike>My guess is that this function performs in O(n•ln(n)) time.</strike>  Looks like my function performs roughly in O(n).  Can it be done in O(ln(n))?</p>