diff --git a/mercurial/localrepo.py b/mercurial/localrepo.py
--- a/mercurial/localrepo.py
+++ b/mercurial/localrepo.py
@@ -315,6 +315,8 @@ class localrepository(repo.repository):
             self.nodetagscache = {}
             for t, n in self.tags().iteritems():
                 self.nodetagscache.setdefault(n, []).append(t)
+            for tags in self.nodetagscache.itervalues():
+                tags.sort()
         return self.nodetagscache.get(node, [])
 
     def _branchtags(self, partial, lrev):
diff --git a/tests/test-bookmarks-rebase.out b/tests/test-bookmarks-rebase.out
--- a/tests/test-bookmarks-rebase.out
+++ b/tests/test-bookmarks-rebase.out
@@ -17,9 +17,9 @@ adding file changes
 added 1 changesets with 1 changes to 1 files (-1 heads)
 rebase completed
 changeset:   3:9163974d1cb5
+tag:         one
 tag:         tip
 tag:         two
-tag:         one
 parent:      1:925d80f479bb
 parent:      2:db815d6d32e6
 user:        test
diff --git a/tests/test-mq-qimport.out b/tests/test-mq-qimport.out
--- a/tests/test-mq-qimport.out
+++ b/tests/test-mq-qimport.out
@@ -6,10 +6,10 @@ applying email
 now at: email
 % hg tip -v
 changeset:   0:1a706973a7d8
+tag:         email
+tag:         qbase
 tag:         qtip
 tag:         tip
-tag:         email
-tag:         qbase
 user:        Username in patch <test@example.net>
 date:        Thu Jan 01 00:00:00 1970 +0000
 files:       x
diff --git a/tests/test-mq.out b/tests/test-mq.out
--- a/tests/test-mq.out
+++ b/tests/test-mq.out
@@ -357,8 +357,8 @@ errors during apply, please fix and refr
 ? foo.rej
 % mq tags
 0 qparent
-1 qbase foo
-2 qtip bar tip
+1 foo qbase
+2 bar qtip tip
 % bad node in status
 popping bar
 now at: foo
@@ -577,10 +577,10 @@ diff -r 9ecee4f634e3 hello.txt
  hello
 +world
 changeset:   1:bf5fc3f07a0a
+tag:         empty
+tag:         qbase
 tag:         qtip
 tag:         tip
-tag:         empty
-tag:         qbase
 user:        test
 date:        Thu Jan 01 00:00:00 1970 +0000
 summary:     imported patch empty
diff --git a/tests/test-qrecord.out b/tests/test-qrecord.out
--- a/tests/test-qrecord.out
+++ b/tests/test-qrecord.out
@@ -110,10 +110,10 @@ examine changes to 'dir/a.txt'? [Ynsfdaq
 
 % after qrecord a.patch 'tip'
 changeset:   1:5d1ca63427ee
+tag:         a.patch
+tag:         qbase
 tag:         qtip
 tag:         tip
-tag:         a.patch
-tag:         qbase
 user:        test
 date:        Thu Jan 01 00:00:00 1970 +0000
 summary:     aaa
@@ -185,9 +185,9 @@ record change 3/3 to 'dir/a.txt'? [Ynsfd
 
 % after qrecord b.patch 'tip'
 changeset:   2:b056198bf878
+tag:         b.patch
 tag:         qtip
 tag:         tip
-tag:         b.patch
 user:        test
 date:        Thu Jan 01 00:00:00 1970 +0000
 summary:     bbb
diff --git a/tests/test-rebase-mq-skip.out b/tests/test-rebase-mq-skip.out
--- a/tests/test-rebase-mq-skip.out
+++ b/tests/test-rebase-mq-skip.out
@@ -13,7 +13,7 @@ adding manifests
 adding file changes
 added 2 changesets with 2 changes to 2 files
 rebase completed
-@  3 P0 tags: p0.patch qtip tip qbase
+@  3 P0 tags: p0.patch qbase qtip tip
 |
 o  2 P1 tags: qparent
 |
diff --git a/tests/test-rebase-mq.out b/tests/test-rebase-mq.out
--- a/tests/test-rebase-mq.out
+++ b/tests/test-rebase-mq.out
@@ -1,5 +1,5 @@
 1 files updated, 0 files merged, 0 files removed, 0 files unresolved
-@  3 P1 tags: qtip tip f2.patch
+@  3 P1 tags: f2.patch qtip tip
 |
 o  2 P0 tags: f.patch qbase
 |
@@ -34,7 +34,7 @@ adding manifests
 adding file changes
 added 2 changesets with 2 changes to 1 files
 rebase completed
-@  3 P1 tags: qtip tip f2.patch
+@  3 P1 tags: f2.patch qtip tip
 |
 o  2 P0 tags: f.patch qbase
 |
diff --git a/tests/test-tag.out b/tests/test-tag.out
--- a/tests/test-tag.out
+++ b/tests/test-tag.out
@@ -49,9 +49,9 @@ abort: '\n' cannot be used in a tag name
 abort: ':' cannot be used in a tag name
 % cloning local tags
 changeset:   0:0acdaf898367
-tag:         foobar
 tag:         bleah
 tag:         bleah0
+tag:         foobar
 user:        test
 date:        Mon Jan 12 13:46:40 1970 +0000
 summary:     test