diff -r 752f77ef7202 -r a4ab37ca887b mercurial/branchmap.py
--- a/mercurial/branchmap.py	Wed Dec 12 02:38:14 2012 +0100
+++ b/mercurial/branchmap.py	Tue Jan 15 02:59:12 2013 +0100
@@ -135,7 +135,7 @@
             if self.filteredhash is not None:
                 cachekey.append(hex(self.filteredhash))
             f.write(" ".join(cachekey) + '\n')
-            for label, nodes in self.iteritems():
+            for label, nodes in sorted(self.iteritems()):
                 for node in nodes:
                     f.write("%s %s\n" % (hex(node), encoding.fromlocal(label)))
             f.close()