diff --git a/mercurial/obsolete.py b/mercurial/obsolete.py
--- a/mercurial/obsolete.py
+++ b/mercurial/obsolete.py
@@ -526,7 +526,7 @@ def successorssets(repo, initialnode, ca
             #   Having none means pruned node, multiple successors means split,
             #   single successors are standard replacement.
             #
-            for mark in succmarkers[current]:
+            for mark in sorted(succmarkers[current]):
                 for suc in mark[1]:
                     if suc not in cache:
                         if suc in stackedset:
@@ -563,7 +563,7 @@ def successorssets(repo, initialnode, ca
                 # duplicated entry and successors set that are strict subset of
                 # another one.
                 succssets = []
-                for mark in succmarkers[current]:
+                for mark in sorted(succmarkers[current]):
                     # successors sets contributed by this marker
                     markss = [[]]
                     for suc in mark[1]:
diff --git a/tests/test-obsolete-divergent.t b/tests/test-obsolete-divergent.t
--- a/tests/test-obsolete-divergent.t
+++ b/tests/test-obsolete-divergent.t
@@ -76,8 +76,8 @@ A_1 have two direct and divergent succes
   d20a80d4def3
       d20a80d4def3
   007dc284c1f8
+      82623d38b9ba
       392fd25390da
-      82623d38b9ba
   82623d38b9ba
       82623d38b9ba
   392fd25390da
@@ -123,8 +123,8 @@ indirect divergence with known changeset
   d20a80d4def3
       d20a80d4def3
   007dc284c1f8
+      82623d38b9ba
       01f36c5a8fda
-      82623d38b9ba
   82623d38b9ba
       82623d38b9ba
   392fd25390da
@@ -158,8 +158,8 @@ indirect divergence with known changeset
   d20a80d4def3
       d20a80d4def3
   007dc284c1f8
+      82623d38b9ba
       392fd25390da
-      82623d38b9ba
   82623d38b9ba
       82623d38b9ba
   392fd25390da