<p>Given a list of sets:</p>

<ul>
<li>S_1 : [ 1, 2, 3, 4 ]</li>
<li>S_2 : [ 3, 4, 5, 6, 7 ]</li>
<li>S_3 : [ 8, 9, 10, 11 ]</li>
<li>S_4 : [ 1, 8, 12, 13 ]</li>
<li>S_5 : [ 6, 7, 14, 15, 16, 17 ]</li>
</ul>

<p>What the most efficient way to merge all sets that share at least 2 elements?  I suppose this is similar to a connected components problem.  So the result would be:</p>

<ul>
<li>[ 1, 2, 3, 4, 5, 6, 7, 14, 15, 16, 17] (S_1 UNION S_2 UNION S_5)</li>
<li>[ 8, 9, 10, 11 ]</li>
<li>[ 1, 8, 12, 13 ] (S_4 shares 1 with S_1, and 8 with S_3, but not merged because they only share one element in each)</li>
</ul>

<p>The naive implementation is O(N^2), where N is the number of sets, which is unworkable for us.  This would need to be efficient for millions of sets.</p>

If you can order the elements in the set, you can look into using
Mergesort
on the sets. The only modification needed is to check for duplicates during the merge phase. If one is found, just discard the duplicate. Since mergesort is O(n*log(n)), this will offer imrpoved speed when compared to the naive O(n^2) algorithm.
However, to really be effective, you should maintain a sorted set and keep it sorted, so that  you can skip the sort phase and go straight to the merge phase.