Index: include/llvm/ADT/STLExtras.h
===================================================================
--- include/llvm/ADT/STLExtras.h
+++ include/llvm/ADT/STLExtras.h
@@ -341,6 +341,46 @@
         reinterpret_cast<int (*)(const void *, const void *)>(Compare));
 }
 
+template <class IteratorTy, class ValueTy>
+inline void multikey_qsort(
+    IteratorTy Start, IteratorTy End,
+    const ValueTy *(*getKey)(IteratorTy, size_t Pos),
+    int (*Compare)(const ValueTy *, const ValueTy *),
+    size_t Pos = 0) {
+  while (End - Start >= 2) {
+    // Partition items. Items in [Start, P) are less than the pivot, [P, Q)
+    // are the same as the pivot, and [Q, End) are greater than the pivot.
+    const ValueTy *Pivot = getKey(Start, Pos);
+    IteratorTy P = Start;
+    IteratorTy Q = End;
+    for (IteratorTy R = Start + 1; R < Q;) {
+      int Comp = Compare(Pivot, getKey(R, Pos));
+      if (Comp < 0)
+        std::swap(*P++, *R++);
+      else if (Comp > 0)
+        std::swap(*--Q, *R);
+      else
+        R++;
+    }
+
+    multikey_qsort(Start, P, getKey, Compare, Pos);
+    multikey_qsort(Q, End, getKey, Compare, Pos);
+
+    // Pivot is null if (*Start)'s size is shorter than Pos.
+    // If we are sorting strings, that means Pos is beyond end of *Start.
+    // In that's the case, we have already sorted all items in [P, Q).
+    if (!Pivot)
+      return;
+
+    // Repeat again with a new range. This is equivalent to
+    // multikey_qsort(P, Q, getKey, Compare, Pos + 1) but does not consume
+    // the stack.
+    Start = P;
+    End = Q;
+    ++Pos;
+  }
+}
+
 //===----------------------------------------------------------------------===//
 //     Extra additions to <algorithm>
 //===----------------------------------------------------------------------===//
Index: lib/MC/StringTableBuilder.cpp
===================================================================
--- lib/MC/StringTableBuilder.cpp
+++ lib/MC/StringTableBuilder.cpp
@@ -18,48 +18,20 @@
 
 StringTableBuilder::StringTableBuilder(Kind K) : K(K) {}
 
-typedef std::pair<StringRef, size_t> StringPair;
-
 // Returns the character at Pos from end of a string.
-static int charTailAt(StringPair *P, size_t Pos) {
-  StringRef S = P->first;
+static const char *charTailAt(
+    std::vector<std::pair<StringRef, size_t> *>::iterator It, size_t Pos) {
+  StringRef S = (*It)->first;
   if (Pos >= S.size())
-    return -1;
-  return (unsigned char)S[S.size() - Pos - 1];
+    return nullptr;
+  return S.data() + S.size() - Pos - 1;
 }
 
-// Three-way radix quicksort. This is much faster than std::sort with strcmp
-// because it does not compare characters that we already know the same.
-static void qsort(StringPair **Begin, StringPair **End, int Pos) {
-tailcall:
-  if (End - Begin <= 1)
-    return;
-
-  // Partition items. Items in [Begin, P) are greater than the pivot,
-  // [P, Q) are the same as the pivot, and [Q, End) are less than the pivot.
-  int Pivot = charTailAt(*Begin, Pos);
-  StringPair **P = Begin;
-  StringPair **Q = End;
-  for (StringPair **R = Begin + 1; R < Q;) {
-    int C = charTailAt(*R, Pos);
-    if (C > Pivot)
-      std::swap(*P++, *R++);
-    else if (C < Pivot)
-      std::swap(*--Q, *R);
-    else
-      R++;
-  }
-
-  qsort(Begin, P, Pos);
-  qsort(Q, End, Pos);
-  if (Pivot != -1) {
-    // qsort(P, Q, Pos + 1), but with tail call optimization.
-    Begin = P;
-    End = Q;
-    ++Pos;
-    goto tailcall;
-  }
-}
+static int compare(const char *A, const char *B) {
+  int X = A ? (unsigned char)*A : -1;
+  int Y = B ? (unsigned char)*B : -1;
+  return X - Y;
+};
 
 void StringTableBuilder::finalize() {
   std::vector<std::pair<StringRef, size_t> *> Strings;
@@ -67,8 +39,9 @@
   for (std::pair<StringRef, size_t> &P : StringIndexMap)
     Strings.push_back(&P);
 
-  if (!Strings.empty())
-    qsort(&Strings[0], &Strings[0] + Strings.size(), 0);
+  // Sort strings by suffix so that strings with the same common suffix
+  // are next to each other in the vector.
+  multikey_qsort(Strings.begin(), Strings.end(), charTailAt, compare);
 
   switch (K) {
   case RAW: