--- 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

--- a/tests/test-copy-move-merge.t	Wed Dec 12 02:38:14 2012 +0100
+++ b/tests/test-copy-move-merge.t	Tue Jan 15 02:59:12 2013 +0100
@@ -31,8 +31,8 @@
   resolving manifests
    overwrite: False, partial: False
    ancestor: b8bf91eeebbc, local: add3f11052fa+, remote: 17c05bb7fcb6
+   a: remote moved to b -> m
    a: remote moved to c -> m
-   a: remote moved to b -> m
   preserving a for resolve of b
   preserving a for resolve of c
   removing a

--- a/tests/test-graft.t	Wed Dec 12 02:38:14 2012 +0100
+++ b/tests/test-graft.t	Tue Jan 15 02:59:12 2013 +0100
@@ -158,8 +158,8 @@
   resolving manifests
    overwrite: False, partial: False
    ancestor: 4c60f11aa304, local: 1905859650ec+, remote: 9c233e8e184d
+   d: remote is newer -> g
    e: versions differ -> m
-   d: remote is newer -> g
   preserving e for resolve of e
   updating: d 1/2 files (50.00%)
   getting d

--- a/tests/test-rename-dir-merge.t	Wed Dec 12 02:38:14 2012 +0100
+++ b/tests/test-rename-dir-merge.t	Tue Jan 15 02:59:12 2013 +0100
@@ -39,9 +39,9 @@
   resolving manifests
    overwrite: False, partial: False
    ancestor: f9b20c0d4c51, local: ce36d17b18fb+, remote: 397f8b00a740
-   a/c: remote renamed directory to b/c -> d
+   a/a: other deleted -> r
    a/b: other deleted -> r
-   a/a: other deleted -> r
+   a/c: remote renamed directory to b/c -> d
    b/a: remote created -> g
    b/b: remote created -> g
   updating: a/a 1/5 files (20.00%)

--- a/tests/test-update-reverse.t	Wed Dec 12 02:38:14 2012 +0100
+++ b/tests/test-update-reverse.t	Tue Jan 15 02:59:12 2013 +0100
@@ -68,8 +68,8 @@
   resolving manifests
    overwrite: True, partial: False
    ancestor: 91ebc10ed028+, local: 91ebc10ed028+, remote: 71a760306caf
+   side1: other deleted -> r
    side2: other deleted -> r
-   side1: other deleted -> r
    main: remote created -> g
   updating: side1 1/3 files (33.33%)
   removing side1