diff --git a/mercurial/context.py b/mercurial/context.py
--- a/mercurial/context.py
+++ b/mercurial/context.py
@@ -598,7 +598,7 @@ class workingctx(changectx):
         return self._parents[0].ancestor(c2) # punt on two parents for now
 
     def walk(self, match):
-        for fn, st in self._repo.dirstate.walk(match, True, False):
+        for fn, st in util.sort(self._repo.dirstate.walk(match, True, False)):
             yield fn
 
 class workingfilectx(filectx):
diff --git a/mercurial/dirstate.py b/mercurial/dirstate.py
--- a/mercurial/dirstate.py
+++ b/mercurial/dirstate.py
@@ -469,8 +469,6 @@ class dirstate(object):
         _join = self._join
         work = []
         wadd = work.append
-        found = []
-        add = found.append
 
         seen = {'.hg': 1}
 
@@ -532,14 +530,12 @@ class dirstate(object):
                     if not ignore(nf):
                         wadd(nf)
                     if nf in dmap and match(nf):
-                        add((nf, None))
+                        yield nf, None
                 elif imatch(nf):
                     if supported(nf, st.st_mode):
-                        add((nf, st))
+                        yield nf, st
                     elif nf in dmap:
-                        add((nf, None))
-        for e in util.sort(found):
-            yield e
+                        yield nf, None
 
         # step 3: report unseen items in the dmap hash
         for f in util.sort(dmap):
diff --git a/mercurial/localrepo.py b/mercurial/localrepo.py
--- a/mercurial/localrepo.py
+++ b/mercurial/localrepo.py
@@ -968,8 +968,6 @@ class localrepository(repo.repository):
         if working: # we need to scan the working dir
             s = self.dirstate.status(match, listignored, listclean, listunknown)
             cmp, modified, added, removed, deleted, unknown, ignored, clean = s
-            removed.sort()
-            deleted.sort()
 
             # check for any possibly clean files
             if parentworking and cmp:
@@ -982,9 +980,8 @@ class localrepository(repo.repository):
                     else:
                         fixup.append(f)
 
-                modified.sort()
                 if listclean:
-                    clean = util.sort(clean + fixup)
+                    clean += fixup
 
                 # update dirstate for files that are actually clean
                 if fixup:
@@ -1017,7 +1014,7 @@ class localrepository(repo.repository):
                 mf2 = mfmatches(ctx2)
 
             modified, added, clean = [], [], []
-            for fn in util.sort(mf2):
+            for fn in mf2:
                 if fn in mf1:
                     if (mf1.flags(fn) != mf2.flags(fn) or
                         (mf1[fn] != mf2[fn] and
@@ -1028,9 +1025,11 @@ class localrepository(repo.repository):
                     del mf1[fn]
                 else:
                     added.append(fn)
-            removed = util.sort(mf1.keys())
+            removed = mf1.keys()
 
-        return modified, added, removed, deleted, unknown, ignored, clean
+        r = modified, added, removed, deleted, unknown, ignored, clean
+        [l.sort() for l in r]
+        return r
 
     def add(self, list):
         wlock = self.wlock()
diff --git a/tests/test-addremove-similar.out b/tests/test-addremove-similar.out
--- a/tests/test-addremove-similar.out
+++ b/tests/test-addremove-similar.out
@@ -10,8 +10,8 @@ adding another-empty-file
 removing empty-file
 adding large-file
 adding tiny-file
+removing large-file
 adding small-file
-removing large-file
 removing tiny-file
 recording removal of tiny-file as rename to small-file (82% similar)
 % should all fail
diff --git a/tests/test-addremove.out b/tests/test-addremove.out
--- a/tests/test-addremove.out
+++ b/tests/test-addremove.out
@@ -8,8 +8,8 @@ dir/bar_2
 foo_2
 adding a
 adding c
+removing a
 adding b
+removing c
 adding d
-removing a
-removing c
 recording removal of a as rename to b (100% similar)