diff -r 2c2564280900 -r fe8caf28d580 mercurial/repair.py
--- a/mercurial/repair.py	Tue Dec 04 12:54:18 2012 -0800
+++ b/mercurial/repair.py	Wed Dec 05 14:33:15 2012 -0800
@@ -112,8 +112,10 @@
         saverevs.difference_update(descendants)
     savebases = [cl.node(r) for r in saverevs]
     stripbases = [cl.node(r) for r in tostrip]
-    newbmtarget = repo.revs('sort(heads((::%ld) - (%ld)), -rev)',
-                            tostrip, tostrip)
+
+    # For a set s, max(parents(s) - s) is the same as max(heads(::s - s)), but
+    # is much faster
+    newbmtarget = repo.revs('max(parents(%ld) - (%ld))', tostrip, tostrip)
     if newbmtarget:
         newbmtarget = repo[newbmtarget[0]].node()
     else: