diff --git a/mercurial/localrepo.py b/mercurial/localrepo.py
--- a/mercurial/localrepo.py
+++ b/mercurial/localrepo.py
@@ -832,7 +832,10 @@ class localrepository(repo.repository):
 
         if node:
             fdict = dict.fromkeys(files)
-            for fn in self.manifest.read(self.changelog.read(node)[0]):
+            mdict = self.manifest.read(self.changelog.read(node)[0])
+            mfiles = mdict.keys()
+            mfiles.sort()
+            for fn in mfiles:
                 for ffn in fdict:
                     # match if the file is the exact name or a directory
                     if ffn == fn or fn.startswith("%s/" % ffn):
@@ -840,7 +843,9 @@ class localrepository(repo.repository):
                         break
                 if match(fn):
                     yield 'm', fn
-            for fn in fdict:
+            ffiles = fdict.keys()
+            ffiles.sort()
+            for fn in ffiles:
                 if badmatch and badmatch(fn):
                     if match(fn):
                         yield 'b', fn
diff --git a/tests/test-locate.out b/tests/test-locate.out
--- a/tests/test-locate.out
+++ b/tests/test-locate.out
@@ -16,9 +16,9 @@ t/x
 a
 NONEXISTENT: No such file in rev ce18e5bc5cd3
 a
-t/x
 b
 t.h
+t/x
 % -I/-X with relative path should work
 b
 t.h