diff --git a/mercurial/discovery.py b/mercurial/discovery.py
--- a/mercurial/discovery.py
+++ b/mercurial/discovery.py
@@ -355,16 +355,15 @@ def checkheads(pushop):
                                                          allfuturecommon,
                                                          newheads)
         newhs.update(unsyncedheads)
-        unsynced = sorted(h for h in unsyncedheads if h not in discardedheads)
-        if unsynced:
-            if None in unsynced:
+        if unsyncedheads:
+            if None in unsyncedheads:
                 # old remote, no heads data
                 heads = None
-            elif len(unsynced) <= 4 or repo.ui.verbose:
-                heads = ' '.join(short(h) for h in unsynced)
+            elif len(unsyncedheads) <= 4 or repo.ui.verbose:
+                heads = ' '.join(short(h) for h in unsyncedheads)
             else:
-                heads = (' '.join(short(h) for h in unsynced[:4]) +
-                         ' ' + _("and %s others") % (len(unsynced) - 4))
+                heads = (' '.join(short(h) for h in unsyncedheads[:4]) +
+                         ' ' + _("and %s others") % (len(unsyncedheads) - 4))
             if heads is None:
                 repo.ui.status(_("remote has heads that are "
                                  "not known locally\n"))