Index: ELF/CallGraphSort.cpp
===================================================================
--- ELF/CallGraphSort.cpp
+++ ELF/CallGraphSort.cpp
@@ -46,6 +46,9 @@
 #include "SymbolTable.h"
 #include "Symbols.h"
 
+#include <list>
+#include <numeric>
+
 using namespace llvm;
 using namespace lld;
 using namespace lld::elf;
@@ -68,7 +71,7 @@
     return double(Weight) / double(Size);
   }
 
-  std::vector<int> Sections;
+  std::list<int> Sections;
   size_t Size = 0;
   uint64_t Weight = 0;
   uint64_t InitialWeight = 0;
@@ -155,12 +158,22 @@
   return false;
 }
 
+// Find the leader of V's belonged cluster (represented as an equivalence
+// class). We apply union-find path-halving technique (simple to implement) in
+// the meantime as it decreases depths and the time complexity.
+static int getLeader(std::vector<int> &Leaders, int V) {
+  while (Leaders[V] != V) {
+    Leaders[V] = Leaders[Leaders[V]];
+    V = Leaders[V];
+  }
+  return V;
+}
+
 static void mergeClusters(Cluster &Into, Cluster &From) {
-  Into.Sections.insert(Into.Sections.end(), From.Sections.begin(),
-                       From.Sections.end());
+  // Merging two lists this way has O(1) time complexity.
+  Into.Sections.splice(Into.Sections.end(), From.Sections);
   Into.Size += From.Size;
   Into.Weight += From.Weight;
-  From.Sections.clear();
   From.Size = 0;
   From.Weight = 0;
 }
@@ -168,42 +181,36 @@
 // Group InputSections into clusters using the Call-Chain Clustering heuristic
 // then sort the clusters by density.
 void CallGraphSort::groupClusters() {
-  std::vector<int> SortedSecs(Clusters.size());
-  std::vector<Cluster *> SecToCluster(Clusters.size());
+  std::vector<int> Sorted(Clusters.size());
+  std::vector<int> Leaders(Clusters.size());
 
-  for (size_t I = 0; I < Clusters.size(); ++I) {
-    SortedSecs[I] = I;
-    SecToCluster[I] = &Clusters[I];
-  }
-
-  std::stable_sort(SortedSecs.begin(), SortedSecs.end(), [&](int A, int B) {
-    return Clusters[B].getDensity() < Clusters[A].getDensity();
+  std::iota(Leaders.begin(), Leaders.end(), 0);
+  std::iota(Sorted.begin(), Sorted.end(), 0);
+  std::stable_sort(Sorted.begin(), Sorted.end(), [&](int A, int B) {
+    return Clusters[A].getDensity() > Clusters[B].getDensity();
   });
 
-  for (int SI : SortedSecs) {
-    // Clusters[SI] is the same as SecToClusters[SI] here because it has not
-    // been merged into another cluster yet.
-    Cluster &C = Clusters[SI];
+  for (int L : Sorted) {
+    // The cluster index is the same as the index of its leader here because
+    // Clusters[L] has not been merged into another cluster yet.
+    Cluster &C = Clusters[L];
 
     // Don't consider merging if the edge is unlikely.
     if (C.BestPred.From == -1 || C.BestPred.Weight * 10 <= C.InitialWeight)
       continue;
 
-    Cluster *PredC = SecToCluster[C.BestPred.From];
-    if (PredC == &C)
+    int PredL = getLeader(Leaders, C.BestPred.From);
+    if (L == PredL)
       continue;
 
+    Cluster *PredC = &Clusters[PredL];
     if (C.Size + PredC->Size > MAX_CLUSTER_SIZE)
       continue;
 
     if (isNewDensityBad(*PredC, C))
       continue;
 
-    // NOTE: Consider using a disjoint-set to track section -> cluster mapping
-    // if this is ever slow.
-    for (int SI : C.Sections)
-      SecToCluster[SI] = PredC;
-
+    Leaders[L] = PredL;
     mergeClusters(*PredC, C);
   }