Index: src/Fragmentation/KeySetsContainer.cpp
===================================================================
--- src/Fragmentation/KeySetsContainer.cpp	(revision 6471481ec9acf0c6a8300253d844532826cc611a)
+++ src/Fragmentation/KeySetsContainer.cpp	(revision 34af9735fd1d2bc3071402d29574e401ed602918)
@@ -42,4 +42,5 @@
 #include <boost/tokenizer.hpp>
 
+#include "CodePatterns/Assert.hpp"
 #include "CodePatterns/Log.hpp"
 
@@ -247,9 +248,37 @@
 void KeySetsContainer::insert(const KeySetsContainer &other)
 {
-  KeySets.reserve(KeySets.size()+other.KeySets.size());
-  AtomCounter.reserve(AtomCounter.size()+other.AtomCounter.size());
-  for (ArrayOfIntVectors::const_iterator iter = other.KeySets.begin();
-      iter != other.KeySets.end(); ++iter)
-    insert(*iter, iter->size());
+  // append sets and their atom count
+  KeySets.insert(KeySets.end(), other.KeySets.begin(), other.KeySets.end());
+  AtomCounter.insert(AtomCounter.end(), other.AtomCounter.begin(), other.AtomCounter.end());
+
+  // ASSUME: that the fragments inside other are number consecutively
+
+  // find the smallest number
+  int smallest_index = std::numeric_limits<int>::max();
+  for(size_t i=0;i<other.OrderSet.size();++i)
+    for(IntVector::const_iterator iter = other.OrderSet[i].begin();
+        iter != other.OrderSet[i].end(); ++iter)
+      smallest_index = std::min(smallest_index, (*iter));
+
+  // renumber incoming fragments and insert into OrderSets
+  int nr_fragments = 0;
+  for(size_t i=0;i<other.OrderSet.size();++i) {
+    for(IntVector::const_iterator iter = other.OrderSet[i].begin();
+        iter != other.OrderSet[i].end(); ++iter) {
+      if (i >= OrderSet.size() )
+        OrderSet.resize(i+1);
+      OrderSet[i].push_back((*iter)+FragmentCounter-smallest_index);
+      if (i >= FragmentsPerOrder.size())
+        FragmentsPerOrder.resize(i+1);
+      ++(FragmentsPerOrder[i]);
+    }
+    nr_fragments += other.OrderSet[i].size();
+  }
+  Order = std::max(Order, other.Order);
+  // the following assert must not necessarily be true because of cycles: 
+  // Order 4 with added cycles is still order 4.
+  //ASSERT( Order == (int)OrderSet.size(),
+  //    "KeySetsContainer::insert() - order not max of either container?");
+  FragmentCounter += nr_fragments;
 }
 
Index: src/Fragmentation/unittests/KeySetsContainerUnitTest.cpp
===================================================================
--- src/Fragmentation/unittests/KeySetsContainerUnitTest.cpp	(revision 6471481ec9acf0c6a8300253d844532826cc611a)
+++ src/Fragmentation/unittests/KeySetsContainerUnitTest.cpp	(revision 34af9735fd1d2bc3071402d29574e401ed602918)
@@ -43,4 +43,6 @@
 #include <boost/archive/text_iarchive.hpp>
 
+#include <boost/assign.hpp>
+
 #include "Fragmentation/KeySetsContainer.hpp"
 
@@ -50,4 +52,6 @@
 #include "UnitTestMain.hpp"
 #endif /*HAVE_TESTRUNNER*/
+
+using namespace boost::assign;
 
 /********************************************** Test classes **************************************/
@@ -105,2 +109,177 @@
   delete Keys2;
 };
+
+static void fillKeySetsContainer(KeySetsContainer *_Keys)
+{
+  // insert keysets
+  KeySetsContainer::IntVector keyset;
+  keyset += 1;
+  _Keys->KeySets.push_back(keyset);
+  keyset += 2;
+  _Keys->KeySets.push_back(keyset);
+  keyset += 3;
+  _Keys->KeySets.push_back(keyset);
+  // insert number of keys per keyset
+  _Keys->AtomCounter += 1,2,3;
+  // insert total number of keysets/fragments
+  _Keys->FragmentCounter = 3;
+  // insert maximum number of keys over all contained keysets
+  _Keys->Order = 3;
+  // insert number of keysets with the same number of keys
+  _Keys->FragmentsPerOrder += 1,1,1;
+  // insert keyset index in keysets per same number of keys
+  _Keys->OrderSet.resize(3);
+  _Keys->OrderSet[0] = KeySetsContainer::IntVector(1, 0);
+  _Keys->OrderSet[1] = KeySetsContainer::IntVector(1, 1);
+  _Keys->OrderSet[2] = KeySetsContainer::IntVector(1, 2);
+}
+
+/** UnitTest for insert() into an empty container
+ */
+void KeySetsContainerTest::insertIntoEmptyTest()
+{
+  // fill other container
+  KeySetsContainer *Keys2 = new KeySetsContainer();
+  fillKeySetsContainer(Keys2);
+
+  // insert filled one (Keys2) into empty (Keys)
+  Keys->insert(*Keys2);
+
+  CPPUNIT_ASSERT (*Keys == *Keys2);
+
+  delete Keys2;
+}
+
+/** UnitTest for insert() empty into a filled container
+ */
+void KeySetsContainerTest::insertEmptyIntoTest()
+{
+  // fill other container
+  KeySetsContainer *Keys2 = new KeySetsContainer();
+  fillKeySetsContainer(Keys2);
+
+  // create result container (we know this works from insertIntoEmptyTest())
+  KeySetsContainer *resultKeys = new KeySetsContainer();
+  resultKeys->insert(*Keys2);
+
+  // fill empty (Keys) into filled oned (Keys2)
+  Keys2->insert(*Keys);
+
+  // create empty for comparison
+  KeySetsContainer *emptyKeys = new KeySetsContainer();
+
+  CPPUNIT_ASSERT (*Keys2 == *resultKeys);
+  CPPUNIT_ASSERT (*Keys == *emptyKeys);
+
+  delete Keys2;
+  delete resultKeys;
+  delete emptyKeys;
+}
+
+/** UnitTest for insert() smaller filled into another filled container
+ */
+void KeySetsContainerTest::insertSmallerIntoTest()
+{
+  // fill other container
+  KeySetsContainer *Keys2 = new KeySetsContainer();
+  fillKeySetsContainer(Keys2);
+
+  // fill Keys, too
+  {
+    KeySetsContainer::IntVector keyset;
+    keyset += 2;
+    Keys->KeySets.push_back(keyset);
+    // insert number of keys per keyset
+    Keys->AtomCounter += 1;
+    // insert total number of keysets/fragments
+    Keys->FragmentCounter = 1;
+    // insert maximum number of keys over all contained keysets
+    Keys->Order = 1;
+    // insert number of keysets with the same number of keys
+    Keys->FragmentsPerOrder += 1;
+    // insert keyset index in keysets per same number of keys
+    Keys->OrderSet.resize(1);
+    Keys->OrderSet[0] = KeySetsContainer::IntVector(1, 0);
+  }
+
+  // create comparison container
+  KeySetsContainer *resultKeys = new KeySetsContainer();
+  {
+    fillKeySetsContainer(resultKeys);
+    KeySetsContainer::IntVector keyset;
+    keyset += 2;
+    resultKeys->KeySets.push_back(keyset);
+    resultKeys->AtomCounter += 1;
+    resultKeys->FragmentCounter = 4;
+    resultKeys->Order = 3;
+    resultKeys->FragmentsPerOrder[0] = 2;
+    CPPUNIT_ASSERT( resultKeys->OrderSet.size() == (size_t)3 );
+    resultKeys->OrderSet[0] += 3;
+  }
+
+  // insert smaller into larger one
+  Keys2->insert(*Keys);
+
+  CPPUNIT_ASSERT (*Keys != *Keys2);
+  CPPUNIT_ASSERT (*resultKeys == *Keys2);
+
+  delete Keys2;
+  delete resultKeys;
+}
+
+/** UnitTest for insert() larger filled into another filled container
+ */
+void KeySetsContainerTest::insertLargerIntoTest()
+{
+  // fill other container
+  KeySetsContainer *Keys2 = new KeySetsContainer();
+  fillKeySetsContainer(Keys2);
+
+  // fill Keys, too
+  {
+    KeySetsContainer::IntVector keyset;
+    keyset += 2;
+    Keys->KeySets.push_back(keyset);
+    // insert number of keys per keyset
+    Keys->AtomCounter += 1;
+    // insert total number of keysets/fragments
+    Keys->FragmentCounter = 1;
+    // insert maximum number of keys over all contained keysets
+    Keys->Order = 1;
+    // insert number of keysets with the same number of keys
+    Keys->FragmentsPerOrder += 1;
+    // insert keyset index in keysets per same number of keys
+    Keys->OrderSet.resize(1);
+    Keys->OrderSet[0] = KeySetsContainer::IntVector(1, 0);
+  }
+
+  // create comparison container
+  KeySetsContainer *resultKeys = new KeySetsContainer();
+  {
+    // we know this works from insertIntoEmptyTest()
+    resultKeys->insert(*Keys);
+    // add larger keysets
+    fillKeySetsContainer(resultKeys);
+
+    resultKeys->AtomCounter.clear();
+    resultKeys->AtomCounter += 1,1,2,3;
+    resultKeys->FragmentCounter = 4;
+    resultKeys->FragmentsPerOrder.clear();
+    resultKeys->FragmentsPerOrder += 2,1,1;
+    resultKeys->OrderSet.clear();
+    resultKeys->OrderSet.resize(3);
+    resultKeys->OrderSet[0] = KeySetsContainer::IntVector(1, 0);
+    resultKeys->OrderSet[0] += 1;
+    resultKeys->OrderSet[1] = KeySetsContainer::IntVector(1, 2);
+    resultKeys->OrderSet[2] = KeySetsContainer::IntVector(1, 3);
+  }
+
+  // insert larger into smaller one
+  Keys->insert(*Keys2);
+
+  CPPUNIT_ASSERT (*Keys != *Keys2);
+  CPPUNIT_ASSERT (*resultKeys == *Keys);
+
+  delete Keys2;
+  delete resultKeys;
+}
Index: src/Fragmentation/unittests/KeySetsContainerUnitTest.hpp
===================================================================
--- src/Fragmentation/unittests/KeySetsContainerUnitTest.hpp	(revision 6471481ec9acf0c6a8300253d844532826cc611a)
+++ src/Fragmentation/unittests/KeySetsContainerUnitTest.hpp	(revision 34af9735fd1d2bc3071402d29574e401ed602918)
@@ -26,4 +26,8 @@
     CPPUNIT_TEST ( EqualityTest );
     CPPUNIT_TEST ( SerializationTest );
+    CPPUNIT_TEST ( insertIntoEmptyTest );
+    CPPUNIT_TEST ( insertEmptyIntoTest );
+    CPPUNIT_TEST ( insertSmallerIntoTest );
+    CPPUNIT_TEST ( insertLargerIntoTest );
     CPPUNIT_TEST_SUITE_END();
 
@@ -33,4 +37,8 @@
       void EqualityTest();
       void SerializationTest();
+      void insertIntoEmptyTest();
+      void insertEmptyIntoTest();
+      void insertSmallerIntoTest();
+      void insertLargerIntoTest();
 
 private:
