diff -r 2150e70c0ee1 -r c605e12dd622 hgext/histedit.py
--- a/hgext/histedit.py	Wed Dec 12 02:38:14 2012 +0100
+++ b/hgext/histedit.py	Wed Dec 12 02:38:14 2012 +0100
@@ -720,7 +720,7 @@
         # if nothing got rewritten there is not purpose for this function
         return
     moves = []
-    for bk, old in repo._bookmarks.iteritems():
+    for bk, old in sorted(repo._bookmarks.iteritems()):
         if old == oldtopmost:
             # special case ensure bookmark stay on tip. 
             #