--- a/hgext/histedit.py	Thu Jun 28 08:45:38 2012 -0500
+++ b/hgext/histedit.py	Sat Jun 30 03:34:41 2012 +0200
@@ -476,7 +476,7 @@
             newtip = sorted(replacemap.values(), key=repo.changelog.rev)[-1]
             copybms(oldtip, newtip)
 
-            for old, new in replacemap.iteritems():
+            for old, new in sorted(replacemap.iteritems()):
                 copybms(old, new)
                 # TODO update mq state