diff --git a/hgext/convert/convcmd.py b/hgext/convert/convcmd.py
--- a/hgext/convert/convcmd.py
+++ b/hgext/convert/convcmd.py
@@ -175,7 +175,7 @@ class converter(object):
             revisions without parents. 'parents' must be a mapping of revision
             identifier to its parents ones.
             """
-            visit = parents.keys()
+            visit = sorted(parents)
             seen = set()
             children = {}
             roots = []
diff --git a/tests/test-convert-cvs-detectmerge.t b/tests/test-convert-cvs-detectmerge.t
--- a/tests/test-convert-cvs-detectmerge.t
+++ b/tests/test-convert-cvs-detectmerge.t
@@ -183,8 +183,8 @@ convert to hg
   sorting...
   converting...
   9 add file1 on trunk
-  8 add text
-  7 unrelated change
+  8 unrelated change
+  7 add text
   6 add text [MERGE from v1_0]
   5 add text [MERGE from v1_1]
   4 add file2 on trunk
@@ -204,8 +204,8 @@ complete log
   5: '' add file2 on trunk
   4: '' add text [MERGE from v1_1]
   3: 'v1_1' add text [MERGE from v1_0]
-  2: 'v1_1' unrelated change
-  1: 'v1_0' add text
+  2: 'v1_0' add text
+  1: 'v1_1' unrelated change
   0: '' add file1 on trunk
 
 graphical log
@@ -225,9 +225,9 @@ graphical log
   |\|
   | o    3: 'v1_1' add text [MERGE from v1_0]
   | |\
-  +---o  2: 'v1_1' unrelated change
+  +---o  2: 'v1_0' add text
   | |
-  | o  1: 'v1_0' add text
+  | o  1: 'v1_1' unrelated change
   |/
   o  0: '' add file1 on trunk
   
diff --git a/tests/test-convert-cvs.t b/tests/test-convert-cvs.t
--- a/tests/test-convert-cvs.t
+++ b/tests/test-convert-cvs.t
@@ -91,8 +91,8 @@ a fixed difference from UTC.
   sorting...
   converting...
   2 Initial revision
-  1 import
-  0 ci0
+  1 ci0
+  0 import
   updating tags
   $ hgcat a
   a
@@ -116,10 +116,10 @@ convert fresh repo with --filemap
   sorting...
   converting...
   2 Initial revision
-  1 import
+  1 ci0
+  0 import
   filtering out empty revision
-  repository tip rolled back to revision 0 (undo commit)
-  0 ci0
+  repository tip rolled back to revision 1 (undo commit)
   updating tags
   $ hgcat b/c
   c
@@ -321,9 +321,9 @@ convert again
   |
   o  3 () update tags date: * +0000 files: .hgtags (glob)
   |
-  o  2 () ci0 date: * -1000 files: b/c (glob)
-  |
-  | o  1 (INITIAL) import date: * -1000 files: (glob)
+  | o  2 (INITIAL) import date: * -1000 files: (glob)
+  | |
+  o |  1 () ci0 date: * -1000 files: b/c (glob)
   |/
   o  0 () Initial revision date: * -1000 files: a b/c (glob)
   
diff --git a/tests/test-convert-svn-move.t b/tests/test-convert-svn-move.t
--- a/tests/test-convert-svn-move.t
+++ b/tests/test-convert-svn-move.t
@@ -100,8 +100,8 @@ Convert files being replaced by director
   4 clobber1
   3 clobber2
   2 adddb
-  1 branch
-  0 clobberdir
+  1 clobberdir
+  0 branch
 
   $ cd hg-repo
 
@@ -210,9 +210,7 @@ Test convert progress bar'
                                                               \r (no-eol) (esc)
   \r (no-eol) (esc)
   converting [=============================>            ] 5/7\r (no-eol) (esc)
-  scanning paths [                                      ] 0/3\r (no-eol) (esc)
-  scanning paths [===========>                          ] 1/3\r (no-eol) (esc)
-  scanning paths [========================>             ] 2/3\r (no-eol) (esc)
+  scanning paths [                                      ] 0/1\r (no-eol) (esc)
   getting files [===>                                   ] 1/8\r (no-eol) (esc)
   getting files [========>                              ] 2/8\r (no-eol) (esc)
   getting files [=============>                         ] 3/8\r (no-eol) (esc)
@@ -224,7 +222,9 @@ Test convert progress bar'
                                                               \r (no-eol) (esc)
   \r (no-eol) (esc)
   converting [===================================>      ] 6/7\r (no-eol) (esc)
-  scanning paths [                                      ] 0/1\r (no-eol) (esc)
+  scanning paths [                                      ] 0/3\r (no-eol) (esc)
+  scanning paths [===========>                          ] 1/3\r (no-eol) (esc)
+  scanning paths [========================>             ] 2/3\r (no-eol) (esc)
   getting files [===>                                   ] 1/8\r (no-eol) (esc)
   getting files [========>                              ] 2/8\r (no-eol) (esc)
   getting files [=============>                         ] 3/8\r (no-eol) (esc)
@@ -243,7 +243,7 @@ Test convert progress bar'
   4 clobber1
   3 clobber2
   2 adddb
-  1 branch
-  0 clobberdir
+  1 clobberdir
+  0 branch
 
   $ cd ..