Index: lib/Format/Format.cpp
===================================================================
--- lib/Format/Format.cpp
+++ lib/Format/Format.cpp
@@ -1753,6 +1753,7 @@
 static void sortCppIncludes(const FormatStyle &Style,
                             const SmallVectorImpl<IncludeDirective> &Includes,
                             ArrayRef<tooling::Range> Ranges, StringRef FileName,
+                            StringRef Code,
                             tooling::Replacements &Replaces, unsigned *Cursor) {
   unsigned IncludesBeginOffset = Includes.front().Offset;
   unsigned IncludesEndOffset =
@@ -1788,6 +1789,10 @@
 
   // If the #includes are out of order, we generate a single replacement fixing
   // the entire block. Otherwise, no replacement is generated.
+  // In case Style.IncldueStyle.IncludeBlocks != IBS_Preserve, this check is not
+  // enough as additional newlines might be added or removed across #include
+  // blocks. This we handle below by generating the updated #imclude blocks and
+  // comparing it to the original.
   if (Indices.size() == Includes.size() &&
       std::is_sorted(Indices.begin(), Indices.end()) &&
       Style.IncludeStyle.IncludeBlocks == tooling::IncludeStyle::IBS_Preserve)
@@ -1808,6 +1813,11 @@
     CurrentCategory = Includes[Index].Category;
   }
 
+  // If the #includes are out of order, we generate a single replacement fixing
+  // the entire range of blocks. Otherwise, no replacement is generated.
+  if (result == Code.substr(IncludesBeginOffset, IncludesBlockSize))
+    return;
+
   auto Err = Replaces.add(tooling::Replacement(
       FileName, Includes.front().Offset, IncludesBlockSize, result));
   // FIXME: better error handling. For now, just skip the replacement for the
@@ -1876,8 +1886,8 @@
           MainIncludeFound = true;
         IncludesInBlock.push_back({IncludeName, Line, Prev, Category});
       } else if (!IncludesInBlock.empty() && !EmptyLineSkipped) {
-        sortCppIncludes(Style, IncludesInBlock, Ranges, FileName, Replaces,
-                        Cursor);
+        sortCppIncludes(Style, IncludesInBlock, Ranges, FileName, Code,
+                        Replaces, Cursor);
         IncludesInBlock.clear();
         FirstIncludeBlock = false;
       }
@@ -1887,8 +1897,10 @@
       break;
     SearchFrom = Pos + 1;
   }
-  if (!IncludesInBlock.empty())
-    sortCppIncludes(Style, IncludesInBlock, Ranges, FileName, Replaces, Cursor);
+  if (!IncludesInBlock.empty()) {
+    sortCppIncludes(Style, IncludesInBlock, Ranges, FileName, Code, Replaces,
+                    Cursor);
+  }
   return Replaces;
 }
 
Index: unittests/Format/SortIncludesTest.cpp
===================================================================
--- unittests/Format/SortIncludesTest.cpp
+++ unittests/Format/SortIncludesTest.cpp
@@ -8,6 +8,7 @@
 
 #include "FormatTestUtils.h"
 #include "clang/Format/Format.h"
+#include "llvm/ADT/None.h"
 #include "llvm/Support/Debug.h"
 #include "gtest/gtest.h"
 
@@ -24,9 +25,11 @@
   }
 
   std::string sort(StringRef Code, std::vector<tooling::Range> Ranges,
-                   StringRef FileName = "input.cc") {
+                   StringRef FileName = "input.cc",
+                   unsigned ExpectedNumRanges = 1) {
     auto Replaces = sortIncludes(FmtStyle, Code, Ranges, FileName);
     Ranges = tooling::calculateRangesAfterReplacements(Replaces, Ranges);
+    EXPECT_EQ(ExpectedNumRanges, Replaces.size());
     auto Sorted = applyAllReplacements(Code, Replaces);
     EXPECT_TRUE(static_cast<bool>(Sorted));
     auto Result = applyAllReplacements(
@@ -35,8 +38,10 @@
     return *Result;
   }
 
-  std::string sort(StringRef Code, StringRef FileName = "input.cpp") {
-    return sort(Code, GetCodeRange(Code), FileName);
+  std::string sort(StringRef Code,
+                   StringRef FileName = "input.cpp",
+                   unsigned ExpectedNumRanges = 1) {
+    return sort(Code, GetCodeRange(Code), FileName, ExpectedNumRanges);
   }
 
   unsigned newCursor(llvm::StringRef Code, unsigned Cursor) {
@@ -151,7 +156,7 @@
                  "#include <b>\n"
                  "#include <a>\n"
                  "#include <c>\n"
-                 "/* clang-format onwards */\n"));
+                 "/* clang-format onwards */\n", "input.h", 2));
 }
 
 TEST_F(SortIncludesTest, IncludeSortingCanBeDisabled) {
@@ -161,7 +166,8 @@
             "#include \"b.h\"\n",
             sort("#include \"a.h\"\n"
                  "#include \"c.h\"\n"
-                 "#include \"b.h\"\n"));
+                 "#include \"b.h\"\n",
+                 "input.h", 0));
 }
 
 TEST_F(SortIncludesTest, MixIncludeAndImport) {
@@ -214,7 +220,7 @@
             sort("#include \"a.h\"\n"
                  "#include \"c.h\"\n"
                  "\n"
-                 "#include \"b.h\"\n"));
+                 "#include \"b.h\"\n", "input.h", 0));
 }
 
 TEST_F(SortIncludesTest, SortsAllBlocksWhenMerging) {
@@ -458,7 +464,7 @@
             sort("#include \"important_os_header.h\"\n"
                  "#include \"c_main.h\"\n"
                  "#include \"a_other.h\"\n",
-                 "c_main.cc"));
+                 "c_main.cc", 0));
 }
 
 TEST_F(SortIncludesTest, PriorityGroupsAreSeparatedWhenRegroupping) {
@@ -486,7 +492,7 @@
                  "#include \"c_main.h\"\n"
                  "\n"
                  "#include \"a_other.h\"\n",
-                 "c_main.cc"));
+                 "c_main.cc", 0));
 }
 
 TEST_F(SortIncludesTest, CalculatesCorrectCursorPosition) {
@@ -634,7 +640,17 @@
             sort("<!--;\n"
                  "#include <b>\n"
                  "#include <a>\n"
-                 "-->"));
+                 "-->", "input.h", 0));
+}
+
+TEST_F(SortIncludesTest, DoNotOutputReplacementsForSortedBlocksWithRegrouping) {
+  Style.IncludeBlocks = Style.IBS_Regroup;
+  std::string Code = R"(
+#include "b.h"
+
+#include <a.h>
+)";
+  EXPECT_EQ(Code, sort(Code, "input.h", 0));
 }
 
 } // end namespace