--- a/mercurial/bookmarks.py	Tue May 12 22:20:56 2020 +0200
+++ b/mercurial/bookmarks.py	Thu May 14 10:24:52 2020 -0400
@@ -754,7 +754,8 @@
     if changed:
         tr = trfunc()
         changes = []
-        for b, node, writer, msg in sorted(changed):
+        key = lambda t: (t[0], t[1] or b'')
+        for b, node, writer, msg in sorted(changed, key=key):
             changes.append((b, node))
             writer(msg)
         localmarks.applychanges(repo, tr, changes)