diff --git a/mercurial/localrepo.py b/mercurial/localrepo.py
--- a/mercurial/localrepo.py
+++ b/mercurial/localrepo.py
@@ -2641,8 +2641,8 @@
                         raise
 
                 # update manifest
-                removed = [f for f in sorted(removed) if f in m1 or f in m2]
-                drop = [f for f in removed if f in m]
+                removed = [f for f in removed if f in m1 or f in m2]
+                drop = sorted([f for f in removed if f in m])
                 for f in drop:
                     del m[f]
                 files = changed + removed
diff --git a/mercurial/manifest.py b/mercurial/manifest.py
--- a/mercurial/manifest.py
+++ b/mercurial/manifest.py
@@ -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