diff -r 38d85ec06552 -r 6310180662f5 mercurial/manifest.py
--- a/mercurial/manifest.py	Wed Apr 24 09:39:40 2019 -0700
+++ b/mercurial/manifest.py	Tue May 14 16:30:38 2019 -0700
@@ -1486,8 +1486,8 @@
 
             _checkforbidden(added)
             # combine the changed lists into one sorted iterator
-            work = heapq.merge([(x, False) for x in added],
-                               [(x, True) for x in removed])
+            work = heapq.merge([(x, False) for x in sorted(added)],
+                               [(x, True) for x in sorted(removed)])
 
             arraytext, deltatext = m.fastdelta(self.fulltextcache[p1], work)
             cachedelta = self._revlog.rev(p1), deltatext