diff --git a/src/__phutil_library_map__.php b/src/__phutil_library_map__.php
--- a/src/__phutil_library_map__.php
+++ b/src/__phutil_library_map__.php
@@ -341,6 +341,7 @@
     'PhutilSimpleOptionsLexerTestCase' => 'lexer/__tests__/PhutilSimpleOptionsLexerTestCase.php',
     'PhutilSimpleOptionsTestCase' => 'parser/__tests__/PhutilSimpleOptionsTestCase.php',
     'PhutilSocketChannel' => 'channel/PhutilSocketChannel.php',
+    'PhutilSortVector' => 'utils/PhutilSortVector.php',
     'PhutilSprite' => 'sprites/PhutilSprite.php',
     'PhutilSpriteSheet' => 'sprites/PhutilSpriteSheet.php',
     'PhutilSymbolLoader' => 'symbols/PhutilSymbolLoader.php',
@@ -424,6 +425,7 @@
     'mgroup' => 'utils/utils.php',
     'mpull' => 'utils/utils.php',
     'msort' => 'utils/utils.php',
+    'msortv' => 'utils/utils.php',
     'newv' => 'utils/utils.php',
     'nonempty' => 'utils/utils.php',
     'phlog' => 'error/phlog.php',
@@ -876,6 +878,7 @@
     'PhutilSimpleOptionsLexerTestCase' => 'PhutilTestCase',
     'PhutilSimpleOptionsTestCase' => 'PhutilTestCase',
     'PhutilSocketChannel' => 'PhutilChannel',
+    'PhutilSortVector' => 'Phobject',
     'PhutilSprite' => 'Phobject',
     'PhutilSpriteSheet' => 'Phobject',
     'PhutilSyntaxHighlighter' => 'Phobject',
diff --git a/src/utils/PhutilSortVector.php b/src/utils/PhutilSortVector.php
new file mode 100644
--- /dev/null
+++ b/src/utils/PhutilSortVector.php
@@ -0,0 +1,47 @@
+<?php
+
+final class PhutilSortVector
+  extends Phobject {
+
+  private $parts = array();
+
+  public function addInt($value) {
+    // We need to produce strings for each integer which sort naturally. This
+    // requires some careful manipulation.
+
+    if ($value === ~PHP_INT_MAX) {
+      // For the minimum integer value (usually -9223372036854775808 on 64
+      // bit systems) we just give it a special "A" prefix to make sure it
+      // sorts first.
+      $prefix = 'A';
+    } else if ($value < 0) {
+      // For all other negative values, we give them a "B" prefix, then
+      // subtract the value from the maximum integer. This sorts values
+      // in ascending order when printed.
+      $prefix = 'B';
+      $value = PHP_INT_MAX + $value;
+    } else {
+      // For zero and positive values, we give them a "C" prefix.
+      $prefix = 'C';
+    }
+
+    $this->parts[] = sprintf('%s%020u', $prefix, $value);
+    return $this;
+  }
+
+  public function addString($value) {
+    if (strlen($value) && (strpos("\0", $value) !== false)) {
+      throw new Exception(
+        pht(
+          'String components of a sort vector must not contain NULL bytes.'));
+    }
+
+    $this->parts[] = $value;
+    return $this;
+  }
+
+  public function __toString() {
+    return implode("\0", $this->parts);
+  }
+
+}
diff --git a/src/utils/__tests__/PhutilUtilsTestCase.php b/src/utils/__tests__/PhutilUtilsTestCase.php
--- a/src/utils/__tests__/PhutilUtilsTestCase.php
+++ b/src/utils/__tests__/PhutilUtilsTestCase.php
@@ -817,5 +817,64 @@
     }
   }
 
+  public function testVectorSortInt() {
+    $original = array(
+      ~PHP_INT_MAX,
+      -2147483648,
+      -5,
+      -3,
+      -1,
+      0,
+      1,
+      2,
+      3,
+      100,
+      PHP_INT_MAX,
+    );
+
+    $items = $this->shuffleMap($original);
+
+    foreach ($items as $key => $value) {
+      $items[$key] = (string)id(new PhutilSortVector())
+        ->addInt($value);
+    }
+
+    asort($items, SORT_STRING);
+
+    $this->assertEqual(
+      array_keys($original),
+      array_keys($items));
+  }
+
+  public function testVectorSortString() {
+    $original = array(
+      '',
+      "\1",
+      'A',
+      'AB',
+      'Z',
+      "Z\1",
+      'ZZZ',
+    );
+
+    $items = $this->shuffleMap($original);
+
+    foreach ($items as $key => $value) {
+      $items[$key] = (string)id(new PhutilSortVector())
+        ->addString($value);
+    }
+
+    asort($items, SORT_STRING);
+
+    $this->assertEqual(
+      array_keys($original),
+      array_keys($items));
+  }
+
+  private function shuffleMap(array $map) {
+    $keys = array_keys($map);
+    shuffle($keys);
+    return array_select_keys($map, $keys);
+  }
 
 }
diff --git a/src/utils/utils.php b/src/utils/utils.php
--- a/src/utils/utils.php
+++ b/src/utils/utils.php
@@ -406,6 +406,50 @@
 
 
 /**
+ * Sort a list of objects by a sort vector.
+ *
+ * This sort is stable, well-behaved, and more efficient than `usort()`.
+ *
+ * @param list List of objects to sort.
+ * @param string Name of a method to call on each object. The method must
+ *   return a @{class:PhutilSortVector}.
+ * @return list Objects ordered by the vectors.
+ */
+function msortv(array $list, $method) {
+  $surrogate = mpull($list, $method);
+
+  $index = 0;
+  foreach ($surrogate as $key => $value) {
+    if (!($value instanceof PhutilSortVector)) {
+      throw new Exception(
+        pht(
+          'Objects passed to "%s" must return sort vectors (objects of '.
+          'class "%s") from the specified method ("%s"). One object (with '.
+          'key "%s") did not.',
+          'msortv()',
+          'PhutilSortVector',
+          $method,
+          $key));
+    }
+
+    // Add the original index to keep the sort stable.
+    $value->addInt($index++);
+
+    $surrogate[$key] = (string)$value;
+  }
+
+  asort($surrogate, SORT_STRING);
+
+  $result = array();
+  foreach ($surrogate as $key => $value) {
+    $result[$key] = $list[$key];
+  }
+
+  return $result;
+}
+
+
+/**
  * Sort a list of arrays by the value of some index. This method is identical to
  * @{function:msort}, but operates on a list of arrays instead of a list of
  * objects.