diff --git a/clang/lib/Index/FileIndexRecord.h b/clang/lib/Index/FileIndexRecord.h
--- a/clang/lib/Index/FileIndexRecord.h
+++ b/clang/lib/Index/FileIndexRecord.h
@@ -27,14 +27,13 @@
 private:
   FileID FID;
   bool IsSystem;
-  std::vector<DeclOccurrence> Decls;
+  mutable bool IsSorted = false;
+  mutable std::vector<DeclOccurrence> Decls;
 
 public:
   FileIndexRecord(FileID FID, bool IsSystem) : FID(FID), IsSystem(IsSystem) {}
 
-  ArrayRef<DeclOccurrence> getDeclOccurrencesSortedByOffset() const {
-    return Decls;
-  }
+  ArrayRef<DeclOccurrence> getDeclOccurrencesSortedByOffset() const;
 
   FileID getFileID() const { return FID; }
   bool isSystem() const { return IsSystem; }
diff --git a/clang/lib/Index/FileIndexRecord.cpp b/clang/lib/Index/FileIndexRecord.cpp
--- a/clang/lib/Index/FileIndexRecord.cpp
+++ b/clang/lib/Index/FileIndexRecord.cpp
@@ -17,23 +17,16 @@
 using namespace clang;
 using namespace clang::index;
 
-static void addOccurrence(std::vector<DeclOccurrence> &Decls,
-                          DeclOccurrence Info) {
-  auto IsNextOccurence = [&]() -> bool {
-    if (Decls.empty())
-      return true;
-    auto &Last = Decls.back();
-    return Last.Offset < Info.Offset;
-  };
-
-  if (IsNextOccurence()) {
-    Decls.push_back(std::move(Info));
-    return;
+ArrayRef<DeclOccurrence>
+FileIndexRecord::getDeclOccurrencesSortedByOffset() const {
+  if (!IsSorted) {
+    llvm::stable_sort(Decls,
+                      [](const DeclOccurrence &A, const DeclOccurrence &B) {
+                        return A.Offset < B.Offset;
+                      });
+    IsSorted = true;
   }
-
-  // We keep Decls in order as we need to access them in this order in all cases.
-  auto It = llvm::upper_bound(Decls, Info);
-  Decls.insert(It, std::move(Info));
+  return Decls;
 }
 
 void FileIndexRecord::addDeclOccurence(SymbolRoleSet Roles, unsigned Offset,
@@ -41,13 +34,15 @@
                                        ArrayRef<SymbolRelation> Relations) {
   assert(D->isCanonicalDecl() &&
          "Occurrences should be associated with their canonical decl");
-  addOccurrence(Decls, DeclOccurrence(Roles, Offset, D, Relations));
+  IsSorted = false;
+  Decls.emplace_back(Roles, Offset, D, Relations);
 }
 
 void FileIndexRecord::addMacroOccurence(SymbolRoleSet Roles, unsigned Offset,
                                         const IdentifierInfo *Name,
                                         const MacroInfo *MI) {
-  addOccurrence(Decls, DeclOccurrence(Roles, Offset, Name, MI));
+  IsSorted = false;
+  Decls.emplace_back(Roles, Offset, Name, MI);
 }
 
 void FileIndexRecord::removeHeaderGuardMacros() {