diff -r 4b09e6f7d7de -r 760c0d67ce5e mercurial/merge.py
--- a/mercurial/merge.py	Wed Dec 12 02:38:14 2012 +0100
+++ b/mercurial/merge.py	Tue Jan 15 02:59:12 2013 +0100
@@ -228,7 +228,7 @@
                 break
 
     # Compare manifests
-    for f, n in m1.iteritems():
+    for f, n in sorted(m1.iteritems()):
         if partial and not partial(f):
             continue
         if f in m2:
@@ -274,7 +274,7 @@
             else:
                 act("other deleted", "r", f)
 
-    for f, n in m2.iteritems():
+    for f, n in sorted(m2.iteritems()):
         if partial and not partial(f):
             continue
         if f in m1 or f in copied: # files already visited