diff --git a/mercurial/branchmap.py b/mercurial/branchmap.py
--- a/mercurial/branchmap.py
+++ b/mercurial/branchmap.py
@@ -221,7 +221,7 @@ class branchcache(dict):
 
     def update(self, repo, revgen):
         """Given a branchhead cache, self, that may have extra nodes or be
-        missing heads, and a generator of nodes that are at least a superset of
+        missing heads, and a generator of nodes that are strictly a superset of
         heads missing, this function updates self to be correct.
         """
         cl = repo.changelog
@@ -239,32 +239,26 @@ class branchcache(dict):
         for branch, newheadrevs in newbranches.iteritems():
             bheads = self.setdefault(branch, [])
             bheadrevs = [cl.rev(node) for node in bheads]
-            ctxisnew = bheadrevs and min(newheadrevs) > max(bheadrevs)
-            # Remove duplicates - nodes that are in newheadrevs and are already
-            # in bheadrevs.  This can happen if you strip a node whose parent
-            # was already a head (because they're on different branches).
-            bheadrevs = sorted(set(bheadrevs).union(newheadrevs))
 
-            # Starting from tip means fewer passes over reachable.  If we know
-            # the new candidates are not ancestors of existing heads, we don't
-            # have to examine ancestors of existing heads
-            if ctxisnew:
-                iterrevs = sorted(newheadrevs)
-            else:
-                iterrevs = list(bheadrevs)
+            # This have been tested True on all internal usage of this function.
+            # run it again in case of doubt
+            # assert not (set(bheadrevs) & set(newheadrevs))
+            newheadrevs.sort()
+            bheadrevs.extend(newheadrevs)
+            bheadrevs.sort()
 
             # This loop prunes out two kinds of heads - heads that are
             # superseded by a head in newheadrevs, and newheadrevs that are not
             # heads because an existing head is their descendant.
-            while iterrevs:
-                latest = iterrevs.pop()
+            while newheadrevs:
+                latest = newheadrevs.pop()
                 if latest not in bheadrevs:
                     continue
                 ancestors = set(cl.ancestors([latest], bheadrevs[0]))
                 if ancestors:
                     bheadrevs = [b for b in bheadrevs if b not in ancestors]
             self[branch] = [cl.node(rev) for rev in bheadrevs]
-            tiprev = max(bheadrevs)
+            tiprev = bheadrevs[-1]
             if tiprev > self.tiprev:
                 self.tipnode = cl.node(tiprev)
                 self.tiprev = tiprev
diff --git a/tests/gpg/random_seed b/tests/gpg/random_seed
index 87e0fc699f09c8eaec8d3f34cd5e7c4a287cf85a..44d97c4f6d14178794773d0d6c4f3098c9844072
GIT binary patch
literal 600
zc$@)P0;m0Xl=}J>A^_7VG#ac*>KV0(uqXP+8)FnsUZnRw56}=fG@wF+TPUEuTwyEW
zn>Q`eO7@+o<3D`45X(45rcW+BFB%sRkaLI&yEgQsq>Y~QQ7Pv}#kttz6jeEZUcBWX
z!B;~W<N@r4UW~Y1AB38By8d|r%mzuFZwibnd0m6JdfH(;4Ixc_6Zg-!2?1{E(Vv@s
zg>^521oP_*6o8~sCiZ#qvU;pYJmbt2KT6gWa~KI%mCB?5>OY(Lr<MC+Q`hb{jek{(
z!bnR2AI&`%lSg?bvavPjF3V2~{>}Y9;V>$j69J+E?->(}M>0aI-q2%w5_|YG%NvQr
z)rGExKlt&hd?v0HMd@hr{;-E_MhB()-~M&cqD+aECGXilD5Tyqt@wQDuc@6eD=n`A
zZv(UT<FE9f=Gc`PGCI95Y&b}f;Xjv|wBFab@3zBtYpwm{qg9Y5*XSH>Lt2)1x&R+h
z9&B=1Y%`p&afVm2GIw29DSyvz$@@P`A&QW^fgn()vuAQu+NXSzTp}!2F8>C(Rmz~r
z`b$8%+IE|!;cgD>o^$`!F($Hoi~U5eAT_>p@Km6AR#o@54Yd)6_;Qz1K6(+asI<<(
zhEh-vvtlAS&HXdH(Zk#bAnfEQfiTa(Bv973BiKakl}9~ywSjSbLw>J50CW8Ft$|<=
z8r0&`A8bDHed}}Q|0=~mLBIU!vR~M-EK_i4<04amh7b_}?Tp?swW1j)EvUKr$X?n&
m<BuPid7FlcmY9Dti!O5OQ)jjL_rcYRa>rl+-#GcJwbv@c_AMX)