Index: cfe/trunk/lib/Format/Format.cpp
===================================================================
--- cfe/trunk/lib/Format/Format.cpp
+++ cfe/trunk/lib/Format/Format.cpp
@@ -1853,6 +1853,7 @@
 static void sortJavaImports(const FormatStyle &Style,
                             const SmallVectorImpl<JavaImportDirective> &Imports,
                             ArrayRef<tooling::Range> Ranges, StringRef FileName,
+                            StringRef Code,
                             tooling::Replacements &Replaces) {
   unsigned ImportsBeginOffset = Imports.front().Offset;
   unsigned ImportsEndOffset =
@@ -1868,12 +1869,12 @@
         findJavaImportGroup(Style, Imports[i].Identifier));
   }
   llvm::sort(Indices, [&](unsigned LHSI, unsigned RHSI) {
-        // Negating IsStatic to push static imports above non-static imports.
-        return std::make_tuple(!Imports[LHSI].IsStatic, JavaImportGroups[LHSI],
-                               Imports[LHSI].Identifier) <
-               std::make_tuple(!Imports[RHSI].IsStatic, JavaImportGroups[RHSI],
-                               Imports[RHSI].Identifier);
-      });
+    // Negating IsStatic to push static imports above non-static imports.
+    return std::make_tuple(!Imports[LHSI].IsStatic, JavaImportGroups[LHSI],
+                           Imports[LHSI].Identifier) <
+           std::make_tuple(!Imports[RHSI].IsStatic, JavaImportGroups[RHSI],
+                           Imports[RHSI].Identifier);
+  });
 
   // Deduplicate imports.
   Indices.erase(std::unique(Indices.begin(), Indices.end(),
@@ -1902,6 +1903,11 @@
     CurrentImportGroup = JavaImportGroups[Index];
   }
 
+  // If the imports are out of order, we generate a single replacement fixing
+  // the entire block. Otherwise, no replacement is generated.
+  if (result == Code.substr(Imports.front().Offset, ImportsBlockSize))
+    return;
+
   auto Err = Replaces.add(tooling::Replacement(FileName, Imports.front().Offset,
                                                ImportsBlockSize, result));
   // FIXME: better error handling. For now, just skip the replacement for the
@@ -1967,7 +1973,7 @@
     SearchFrom = Pos + 1;
   }
   if (!ImportsInBlock.empty())
-    sortJavaImports(Style, ImportsInBlock, Ranges, FileName, Replaces);
+    sortJavaImports(Style, ImportsInBlock, Ranges, FileName, Code, Replaces);
   return Replaces;
 }
 
Index: cfe/trunk/unittests/Format/SortImportsTestJava.cpp
===================================================================
--- cfe/trunk/unittests/Format/SortImportsTestJava.cpp
+++ cfe/trunk/unittests/Format/SortImportsTestJava.cpp
@@ -262,6 +262,14 @@
                  "import org.a;"));
 }
 
+TEST_F(SortImportsTestJava, NoReplacementsForValidImports) {
+  // Identical #includes have led to a failure with an unstable sort.
+  std::string Code = "import org.a;\n"
+                     "import org.b;\n";
+  EXPECT_TRUE(
+      sortIncludes(FmtStyle, Code, GetCodeRange(Code), "input.java").empty());
+}
+
 } // end namespace
 } // end namespace format
 } // end namespace clang