diff --git a/mercurial/exchange.py b/mercurial/exchange.py
--- a/mercurial/exchange.py
+++ b/mercurial/exchange.py
@@ -2567,7 +2567,8 @@ def _getbundleobsmarkerpart(
             heads = repo.heads()
         subset = [c.node() for c in repo.set(b'::%ln', heads)]
         markers = repo.obsstore.relevantmarkers(subset)
-        markers = sorted(markers)
+        # last item of marker tuple ('parents') may be None or a tuple
+        markers = sorted(markers, key=lambda m: m[:-1] + (m[-1] or (),))
         bundle2.buildobsmarkerspart(bundler, markers)