diff --git a/mercurial/match.py b/mercurial/match.py
--- a/mercurial/match.py
+++ b/mercurial/match.py
@@ -197,7 +197,7 @@ def match(
 
     Usually a patternmatcher is returned:
     >>> _match(b'/foo', b'.', [br're:.*\.c$', b'path:foo/a', b'*.py'])
-    <patternmatcher patterns='.*\\.c$|foo/a(?:/|$)|[^/]*\\.py$'>
+    <patternmatcher patterns='[^/]*\\.py$|foo/a(?:/|$)|.*\\.c$'>
 
     Combining 'patterns' with 'include' (resp. 'exclude') gives an
     intersectionmatcher (resp. a differencematcher):
@@ -614,7 +614,7 @@ class patternmatcher(basematcher):
     True
 
     >>> m.files()
-    ['', 'foo/a', 'b', '']
+    [b'', b'foo/a', b'', b'b']
     >>> m.exact(b'foo/a')
     True
     >>> m.exact(b'b')
@@ -625,6 +625,7 @@ class patternmatcher(basematcher):
 
     def __init__(self, root, kindpats, badfn=None):
         super(patternmatcher, self).__init__(badfn)
+        kindpats.sort()
 
         self._files = _explicitfiles(kindpats)
         self._prefix = _prefix(kindpats)
diff --git a/tests/test-fileset.t b/tests/test-fileset.t
--- a/tests/test-fileset.t
+++ b/tests/test-fileset.t
@@ -53,7 +53,7 @@ Test operators and basic patterns
       (symbol 'glob')
       (symbol 'b?')))
   * matcher:
-  <patternmatcher patterns='a1(?:/|$)|b.$'>
+  <patternmatcher patterns='b.$|a1(?:/|$)'>
   a1
   b1
   b2
diff --git a/tests/test-walk.t b/tests/test-walk.t
--- a/tests/test-walk.t
+++ b/tests/test-walk.t
@@ -536,7 +536,7 @@ Test patterns:
   f  mammals/Procyonidae/raccoon     mammals/Procyonidae/raccoon
   $ hg debugwalk -v beans 'glob:beans/*'
   * matcher:
-  <patternmatcher patterns='beans(?:/|$)|beans/[^/]*$'>
+  <patternmatcher patterns='beans/[^/]*$|beans(?:/|$)'>
   f  beans/black     beans/black
   f  beans/borlotti  beans/borlotti
   f  beans/kidney    beans/kidney