title: What is an efficient algorithm to compare two large lists of data in C++?
body: <p>I have two lists of times in nanoseconds.  Each list can have 10^12 elements or more.  My current implementation is to take a subset of both lists, compare the times in that subset using for loops and output correlated times, then take another subset.  For each subset comparison this runs in approx. (m*n) where m is the size of list 1 subset and n is the size of the list 2 subset, which is obviously a bad algorithm.</p>
  
  <p>I also have a clock that is smaller than the total time of my data sets, so there are rollovers in the data to be concerned with at certain times.</p>
  
  <p>List 1 has certain events, and list two has secondary events.  I want to know if the secondary events happen within a certain time from the primary events.  There is also a lot of noise, so I need to create a histogram of correlated times and look for a time where there is a statistically significant signal.  </p>
  
  <p>I would like to know if there is a known efficient algorithm that can be used in C++ from any open source library, or an efficient algorithm that I can implement, to search the times of both lists, and output the items that fall within the window.</p>
  
  <p>Here is an example of the brute force function:</p>
  
  <pre><code>int correlate_lists( int window )
  {
    for( int i = 0 ; i &lt; list1.size() ; i++ )
    {  
      for( int j = 0 ; j &lt; list2.size() ; j++ )
      {
        if( list2[j].time() &gt; list1[i].time() &amp;&amp;  (list2[j].time() - list1[j].time()) &lt; window )
        {
          printf("Time: %d\n, list2[j].time() - list[1].time() );
        }
      }
    }
  }
  </code></pre>