Index: lib/fuzzer/FuzzerCorpus.h
===================================================================
--- lib/fuzzer/FuzzerCorpus.h
+++ lib/fuzzer/FuzzerCorpus.h
@@ -294,7 +294,7 @@
   Vector<double> Intervals;
   Vector<double> Weights;
 
-  std::unordered_set<std::string> Hashes;
+  UnorderedSet<std::string> Hashes;
   Vector<InputInfo*> Inputs;
 
   size_t NumAddedFeatures = 0;
Index: lib/fuzzer/FuzzerDefs.h
===================================================================
--- lib/fuzzer/FuzzerDefs.h
+++ lib/fuzzer/FuzzerDefs.h
@@ -15,10 +15,12 @@
 #include <cstddef>
 #include <cstdint>
 #include <cstring>
+#include <memory>
+#include <set>
 #include <string>
+#include <unordered_set>
 #include <vector>
-#include <set>
-#include <memory>
+
 
 // Platform detection.
 #ifdef __linux__
@@ -191,6 +193,10 @@
 template<typename T>
 using Set = std::set<T, std::less<T>, fuzzer_allocator<T>>;
 
+template<typename T>
+using UnorderedSet =
+    std::unordered_set<T, std::hash<T>, std::equal_to<T>, fuzzer_allocator<T>>;
+
 typedef Vector<uint8_t> Unit;
 typedef Vector<Unit> UnitVector;
 typedef int (*UserCallback)(const uint8_t *Data, size_t Size);
Index: lib/fuzzer/FuzzerMerge.cpp
===================================================================
--- lib/fuzzer/FuzzerMerge.cpp
+++ lib/fuzzer/FuzzerMerge.cpp
@@ -221,7 +221,7 @@
       U.resize(MaxInputLen);
       U.shrink_to_fit();
     }
-    std::ostringstream StartedLine;
+
     // Write the pre-run marker.
     OF << "STARTED " << i << " " << U.size() << "\n";
     OF.flush();  // Flush is important since Command::Execute may crash.
@@ -260,22 +260,39 @@
   PrintStatsWrapper("DONE  ");
 }
 
-static void WriteNewControlFile(const std::string &CFPath,
-                                const Vector<SizedFile> &OldCorpus,
-                                const Vector<SizedFile> &NewCorpus) {
-  RemoveFile(CFPath);
-  std::ofstream ControlFile(CFPath);
-  ControlFile << (OldCorpus.size() + NewCorpus.size()) << "\n";
-  ControlFile << OldCorpus.size() << "\n";
+static size_t WriteNewControlFile(const std::string &CFPath,
+                                  const Vector<SizedFile> &OldCorpus,
+                                  const Vector<SizedFile> &NewCorpus,
+                                  const Vector<MergeFileInfo> &KnownFiles) {
+  UnorderedSet<std::string> FilesToSkip;
+  for (auto &SF: KnownFiles)
+    FilesToSkip.insert(SF.Name);
+
+  Vector<std::string> FilesToUse;
+  auto MaybeUseFile = [=, &FilesToUse](std::string Name) {
+    if (FilesToSkip.find(Name) == FilesToSkip.end())
+      FilesToUse.push_back(Name);
+  };
   for (auto &SF: OldCorpus)
-    ControlFile << SF.File << "\n";
+    MaybeUseFile(SF.File);
+  auto FilesToUseFromOldCorpus = FilesToUse.size();
   for (auto &SF: NewCorpus)
-    ControlFile << SF.File << "\n";
+    MaybeUseFile(SF.File);
+
+  RemoveFile(CFPath);
+  std::ofstream ControlFile(CFPath);
+  ControlFile << FilesToUse.size() << "\n";
+  ControlFile << FilesToUseFromOldCorpus << "\n";
+  for (auto &FN: FilesToUse)
+    ControlFile << FN << "\n";
+
   if (!ControlFile) {
     Printf("MERGE-OUTER: failed to write to the control file: %s\n",
            CFPath.c_str());
     exit(1);
   }
+
+  return FilesToUse.size();
 }
 
 // Outer process. Does not call the target code and thus should not fail.
@@ -291,12 +308,13 @@
                          bool V /*Verbose*/) {
   if (NewCorpus.empty() && OldCorpus.empty()) return;  // Nothing to merge.
   size_t NumAttempts = 0;
+  Vector<MergeFileInfo> KnownFiles;
   if (FileSize(CFPath)) {
     VPrintf(V, "MERGE-OUTER: non-empty control file provided: '%s'\n",
            CFPath.c_str());
     Merger M;
     std::ifstream IF(CFPath);
-    if (M.Parse(IF, /*ParseCoverage=*/false)) {
+    if (M.Parse(IF, /*ParseCoverage=*/true)) {
       VPrintf(V, "MERGE-OUTER: control file ok, %zd files total,"
              " first not processed file %zd\n",
              M.Files.size(), M.FirstNotProcessedFile);
@@ -305,12 +323,25 @@
                "(merge has stumbled on it the last time)\n",
                M.LastFailure.c_str());
       if (M.FirstNotProcessedFile >= M.Files.size()) {
-        VPrintf(
-            V, "MERGE-OUTER: nothing to do, merge has been completed before\n");
-        exit(0);
+        // Merge has already been completed with the given merge control file.
+        if (M.Files.size() == OldCorpus.size() + NewCorpus.size()) {
+          VPrintf(
+              V,
+              "MERGE-OUTER: nothing to do, merge has been completed before\n");
+          exit(0);
+        } else {
+          // Number of input files likely changed, start merge from scratch, but
+          // reuse coverage information from the given merge control file.
+          VPrintf(
+              V,
+              "MERGE-OUTER: starting merge from scratch, but reusing coverage "
+              "information from the given control file\n");
+          KnownFiles = M.Files;
+        }
+      } else {
+        // There is a merge in progress, continue.
+        NumAttempts = M.Files.size() - M.FirstNotProcessedFile;
       }
-
-      NumAttempts = M.Files.size() - M.FirstNotProcessedFile;
     } else {
       VPrintf(V, "MERGE-OUTER: bad control file, will overwrite it\n");
     }
@@ -318,10 +349,11 @@
 
   if (!NumAttempts) {
     // The supplied control file is empty or bad, create a fresh one.
-    NumAttempts = OldCorpus.size() + NewCorpus.size();
-    VPrintf(V, "MERGE-OUTER: %zd files, %zd in the initial corpus\n",
-            NumAttempts, OldCorpus.size());
-    WriteNewControlFile(CFPath, OldCorpus, NewCorpus);
+    VPrintf(V, "MERGE-OUTER: "
+            "%zd files, %zd in the initial corpus, %zd processed earlier\n",
+            OldCorpus.size() + NewCorpus.size(), OldCorpus.size(),
+            KnownFiles.size());
+    NumAttempts = WriteNewControlFile(CFPath, OldCorpus, NewCorpus, KnownFiles);
   }
 
   // Execute the inner process until it passes.
@@ -358,6 +390,8 @@
   VPrintf(V,
           "MERGE-OUTER: consumed %zdMb (%zdMb rss) to parse the control file\n",
           M.ApproximateMemoryConsumption() >> 20, GetPeakRSSMb());
+
+  M.Files.insert(M.Files.end(), KnownFiles.begin(), KnownFiles.end());
   M.Merge(InitialFeatures, NewFeatures, InitialCov, NewCov, NewFiles);
   VPrintf(V, "MERGE-OUTER: %zd new files with %zd new features added; "
           "%zd new coverage edges\n",
Index: test/fuzzer/merge.test
===================================================================
--- test/fuzzer/merge.test
+++ test/fuzzer/merge.test
@@ -1,5 +1,3 @@
-CHECK: BINGO
-
 RUN: %cpp_compiler %S/FullCoverageSetTest.cpp -o %t-FullCoverageSetTest
 
 RUN: rm -rf %t/T0 %t/T1 %t/T2
Index: test/fuzzer/merge_two_step.test
===================================================================
--- /dev/null
+++ test/fuzzer/merge_two_step.test
@@ -0,0 +1,31 @@
+RUN: %cpp_compiler %S/FullCoverageSetTest.cpp -o %t-FullCoverageSetTest
+
+RUN: rm -rf %t/T0 %t/T1 %t/T2
+RUN: mkdir -p %t/T0 %t/T1 %t/T2
+RUN: echo F..... > %t/T1/1
+RUN: echo .U.... > %t/T1/2
+RUN: echo ..Z... > %t/T1/3
+
+# T1 has 3 elements, T0 is empty.
+RUN: rm -f %t/MCF
+RUN: %run %t-FullCoverageSetTest -merge=1 -merge_control_file=%t/MCF %t/T0 %t/T1 2>&1 | FileCheck %s --check-prefix=CHECK1
+CHECK1: MERGE-OUTER: 3 files, 0 in the initial corpus
+CHECK1: MERGE-OUTER: 3 new files with 11 new features added; 11 new coverage edges
+
+RUN: echo ...Z.. > %t/T2/1
+RUN: echo ....E. > %t/T2/2
+RUN: echo .....R > %t/T2/3
+RUN: echo F..... > %t/T2/a
+
+RUN: rm -rf %t/T0
+RUN: mkdir -p %t/T0
+
+# T1 has 3 elements, T2 has 4 elements, T0 is empty.
+RUN: %run %t-FullCoverageSetTest -merge=1 -merge_control_file=%t/MCF %t/T0 %t/T1 %t/T2 2>&1 | FileCheck %s --check-prefix=CHECK2
+CHECK2: MERGE-OUTER: non-empty control file provided
+CHECK2: MERGE-OUTER: control file ok, 3 files total, first not processed file 3
+CHECK2: MERGE-OUTER: starting merge from scratch, but reusing coverage information from the given control file
+CHECK2: MERGE-OUTER: 7 files, 0 in the initial corpus, 3 processed earlier
+CHECK2: MERGE-INNER: using the control file 
+CHECK2: MERGE-INNER: 4 total files; 0 processed earlier; will process 4 files now
+CHECK2: MERGE-OUTER: 6 new files with 14 new features added; 14 new coverage edges