Index: lib/Format/Format.cpp
===================================================================
--- lib/Format/Format.cpp
+++ lib/Format/Format.cpp
@@ -1807,19 +1807,21 @@
     if (!FormattingOff && !Line.endswith("\\")) {
       if (IncludeRegex.match(Line, &Matches)) {
         StringRef IncludeName = Matches[2];
-        int Category;
-        if (LookForMainHeader && !IncludeName.startswith("<")) {
-          Category = 0;
-        } else {
-          Category = INT_MAX;
-          for (unsigned i = 0, e = CategoryRegexs.size(); i != e; ++i) {
+        int Category = INT_MAX;
+        for (unsigned i = 0, e = CategoryRegexs.size(); i != e; ++i) {
             if (CategoryRegexs[i].match(IncludeName)) {
-              Category = Style.IncludeCategories[i].Priority;
-              break;
+                Category = Style.IncludeCategories[i].Priority;
+                break;
             }
-          }
         }
-        LookForMainHeader = false;
+
+        if (Category >= 0 ) {
+            if (LookForMainHeader && !IncludeName.startswith("<")) {
+                Category = 0;
+            }
+            LookForMainHeader = false;
+        }
+
         IncludesInBlock.push_back({IncludeName, Line, Prev, Category});
       } else if (!IncludesInBlock.empty()) {
         sortIncludes(Style, IncludesInBlock, Ranges, FileName, Replaces,
Index: unittests/Format/SortIncludesTest.cpp
===================================================================
--- unittests/Format/SortIncludesTest.cpp
+++ unittests/Format/SortIncludesTest.cpp
@@ -188,9 +188,19 @@
 TEST_F(SortIncludesTest, NegativePriorities) {
   Style.IncludeCategories = {{".*important_os_header.*", -1}, {".*", 1}};
   EXPECT_EQ("#include \"important_os_header.h\"\n"
-            "#include \"a.h\"\n",
-            sort("#include \"a.h\"\n"
+            "#include \"c_main_header.h\"\n"
+            "#include \"a_other_header.h\"\n",
+            sort("#include \"c_main_header.h\"\n"
+                 "#include \"a_other_header.h\"\n"
                  "#include \"important_os_header.h\"\n"));
+
+  // check stable when re-run
+  EXPECT_EQ("#include \"important_os_header.h\"\n"
+            "#include \"c_main_header.h\"\n"
+            "#include \"a_other_header.h\"\n",
+            sort("#include \"important_os_header.h\"\n"
+                 "#include \"c_main_header.h\"\n"
+                 "#include \"a_other_header.h\"\n"));
 }
 
 TEST_F(SortIncludesTest, CalculatesCorrectCursorPosition) {