--- a/mercurial/tags.py	Thu Jan 22 12:36:38 2015 -0800
+++ b/mercurial/tags.py	Tue Feb 24 00:06:47 2015 -0800
@@ -337,7 +337,7 @@
     # them local encoding on input, we would lose info writing them to
     # the cache.
     cachefile.write('\n')
-    for (name, (node, hist)) in cachetags.iteritems():
+    for (name, (node, hist)) in sorted(cachetags.iteritems()):
         for n in hist:
             cachefile.write("%s %s\n" % (hex(n), name))
         cachefile.write("%s %s\n" % (hex(node), name))