# HG changeset patch
# User Matt Mackall <mpm@selenic.com>
# Date 2008-06-27 23:28:45
# Node ID f67d1468ac50a88eea7ac2804f646ee3ddbe0c41
# Parent  cb981fc955fba9e95a3c5166d9d9e7e59b9d5ef5

util: add sort helper

diff --git a/hgext/bugzilla.py b/hgext/bugzilla.py
--- a/hgext/bugzilla.py
+++ b/hgext/bugzilla.py
@@ -99,9 +99,7 @@ class bugzilla_2_16(object):
     def filter_real_bug_ids(self, ids):
         '''filter not-existing bug ids from list.'''
         self.run('select bug_id from bugs where bug_id in %s' % buglist(ids))
-        ids = [c[0] for c in self.cursor.fetchall()]
-        ids.sort()
-        return ids
+        return util.sort([c[0] for c in self.cursor.fetchall()])
 
     def filter_unknown_bug_ids(self, node, ids):
         '''filter bug ids from list that already refer to this changeset.'''
@@ -114,9 +112,7 @@ class bugzilla_2_16(object):
             self.ui.status(_('bug %d already knows about changeset %s\n') %
                            (id, short(node)))
             unknown.pop(id, None)
-        ids = unknown.keys()
-        ids.sort()
-        return ids
+        return util.sort(unknown.keys())
 
     def notify(self, ids):
         '''tell bugzilla to send mail.'''
diff --git a/hgext/churn.py b/hgext/churn.py
--- a/hgext/churn.py
+++ b/hgext/churn.py
@@ -92,14 +92,12 @@ def churn(ui, repo, **opts):
             alias, actual = l.split()
             amap[alias] = actual
 
-    revs = [int(r) for r in cmdutil.revrange(repo, opts['rev'])]
-    revs.sort()
+    revs = util.sort([int(r) for r in cmdutil.revrange(repo, opts['rev'])])
     stats = countrevs(ui, repo, amap, revs, opts.get('progress'))
     if not stats:
         return
 
-    stats = [(-l, u, l) for u,l in stats.items()]
-    stats.sort()
+    stats = util.sort([(-l, u, l) for u,l in stats.items()])
     maxchurn = float(max(1, stats[0][2]))
     maxuser = max([len(u) for k, u, l in stats])
 
diff --git a/hgext/convert/cvs.py b/hgext/convert/cvs.py
--- a/hgext/convert/cvs.py
+++ b/hgext/convert/cvs.py
@@ -337,10 +337,7 @@ class convert_cvs(converter_source):
 
     def getchanges(self, rev):
         self.modecache = {}
-        files = self.files[rev]
-        cl = files.items()
-        cl.sort()
-        return (cl, {})
+        return util.sort(self.files[rev].items()), {}
 
     def getcommit(self, rev):
         return self.changeset[rev]
@@ -349,7 +346,4 @@ class convert_cvs(converter_source):
         return self.tags
 
     def getchangedfiles(self, rev, i):
-        files = self.files[rev].keys()
-        files.sort()
-        return files
-
+        return util.sort(self.files[rev].keys())
diff --git a/hgext/convert/cvsps.py b/hgext/convert/cvsps.py
--- a/hgext/convert/cvsps.py
+++ b/hgext/convert/cvsps.py
@@ -297,8 +297,7 @@ def createlog(ui, directory=None, root="
         if store:
             # clean up the results and save in the log.
             store = False
-            e.tags = [scache(x) for x in tags.get(e.revision, [])]
-            e.tags.sort()
+            e.tags = util.sort([scache(x) for x in tags.get(e.revision, [])])
             e.comment = scache('\n'.join(e.comment))
 
             revn = len(e.revision)
@@ -468,9 +467,7 @@ def createchangeset(ui, log, fuzz=60, me
             for tag in e.tags:
                 tags[tag] = True
         # remember tags only if this is the latest changeset to have it
-        tagnames = [tag for tag in tags if globaltags[tag] is c]
-        tagnames.sort()
-        c.tags = tagnames
+        c.tags = util.sort([tag for tag in tags if globaltags[tag] is c])
 
     # Find parent changesets, handle {{mergetobranch BRANCHNAME}}
     # by inserting dummy changesets with two parents, and handle
diff --git a/hgext/convert/darcs.py b/hgext/convert/darcs.py
--- a/hgext/convert/darcs.py
+++ b/hgext/convert/darcs.py
@@ -110,9 +110,8 @@ class darcs_source(converter_source, com
                 copies[elt.get('from')] = elt.get('to')
             else:
                 changes.append((elt.text.strip(), rev))
-        changes.sort()
         self.lastrev = rev
-        return changes, copies
+        return util.sort(changes), copies
 
     def getfile(self, name, rev):
         if rev != self.lastrev:
diff --git a/hgext/convert/gnuarch.py b/hgext/convert/gnuarch.py
--- a/hgext/convert/gnuarch.py
+++ b/hgext/convert/gnuarch.py
@@ -130,10 +130,8 @@ class gnuarch_source(converter_source, c
             for c in cps:
                 copies[c] = cps[c]
 
-        changes.sort()
         self.lastrev = rev
-
-        return changes, copies
+        return util.sort(changes), copies
 
     def getcommit(self, rev):
         changes = self.changes[rev]
diff --git a/hgext/convert/hg.py b/hgext/convert/hg.py
--- a/hgext/convert/hg.py
+++ b/hgext/convert/hg.py
@@ -164,14 +164,11 @@ class mercurial_sink(converter_sink):
              tagparent = nullid
 
          try:
-             old = parentctx.filectx(".hgtags").data()
-             oldlines = old.splitlines(1)
-             oldlines.sort()
+             oldlines = util.sort(parentctx['.hgtags'].data().splitlines(1))
          except:
              oldlines = []
 
-         newlines = [("%s %s\n" % (tags[tag], tag)) for tag in tags.keys()]
-         newlines.sort()
+         newlines = util.sort([("%s %s\n" % (tags[tag], tag)) for tag in tags])
 
          if newlines == oldlines:
              return None
@@ -238,8 +235,7 @@ class mercurial_source(converter_source)
         else:
             m, a, r = self.repo.status(ctx.parents()[0].node(), ctx.node())[:3]
         changes = [(name, rev) for name in m + a + r]
-        changes.sort()
-        return (changes, self.getcopies(ctx, m + a))
+        return util.sort(changes), self.getcopies(ctx, m + a)
 
     def getcopies(self, ctx, files):
         copies = {}
diff --git a/hgext/convert/subversion.py b/hgext/convert/subversion.py
--- a/hgext/convert/subversion.py
+++ b/hgext/convert/subversion.py
@@ -658,8 +658,7 @@ class svn_source(converter_source):
                 # This will fail if a directory was copied
                 # from another branch and then some of its files
                 # were deleted in the same transaction.
-                children = self._find_children(path, revnum)
-                children.sort()
+                children = util.sort(self._find_children(path, revnum))
                 for child in children:
                     # Can we move a child directory and its
                     # parent in the same commit? (probably can). Could
@@ -732,8 +731,7 @@ class svn_source(converter_source):
             parents = []
             # check whether this revision is the start of a branch or part
             # of a branch renaming
-            orig_paths = orig_paths.items()
-            orig_paths.sort()
+            orig_paths = util.sort(orig_paths.items())
             root_paths = [(p,e) for p,e in orig_paths if self.module.startswith(p)]
             if root_paths:
                 path, ent = root_paths[-1]
@@ -1045,10 +1043,9 @@ class svn_sink(converter_sink, commandli
         return dirs
 
     def add_dirs(self, files):
-        add_dirs = [d for d in self.dirs_of(files)
+        add_dirs = [d for d in util.sort(self.dirs_of(files))
                     if not os.path.exists(self.wjoin(d, '.svn', 'entries'))]
         if add_dirs:
-            add_dirs.sort()
             self.xargs(add_dirs, 'add', non_recursive=True, quiet=True)
         return add_dirs
 
@@ -1058,8 +1055,7 @@ class svn_sink(converter_sink, commandli
         return files
 
     def tidy_dirs(self, names):
-        dirs = list(self.dirs_of(names))
-        dirs.sort()
+        dirs = util.sort(self.dirs_of(names))
         dirs.reverse()
         deleted = []
         for d in dirs:
diff --git a/hgext/graphlog.py b/hgext/graphlog.py
--- a/hgext/graphlog.py
+++ b/hgext/graphlog.py
@@ -13,6 +13,7 @@ from mercurial.commands import templateo
 from mercurial.i18n import _
 from mercurial.node import nullrev
 from mercurial.util import Abort, canonpath
+from mercurial import util
 
 def revision_grapher(repo, start_rev, stop_rev):
     """incremental revision grapher
@@ -53,8 +54,7 @@ def revision_grapher(repo, start_rev, st
         for parent in parents:
             if parent not in next_revs:
                 parents_to_add.append(parent)
-        parents_to_add.sort()
-        next_revs[rev_index:rev_index + 1] = parents_to_add
+        next_revs[rev_index:rev_index + 1] = util.sort(parents_to_add)
 
         edges = []
         for parent in parents:
@@ -105,8 +105,7 @@ def filelog_grapher(repo, path, start_re
         for parent in parents:
             if parent not in next_revs:
                 parents_to_add.append(parent)
-        parents_to_add.sort()
-        next_revs[rev_index:rev_index + 1] = parents_to_add
+        next_revs[rev_index:rev_index + 1] = util.sort(parents_to_add)
 
         edges = []
         for parent in parents:
diff --git a/hgext/inotify/server.py b/hgext/inotify/server.py
--- a/hgext/inotify/server.py
+++ b/hgext/inotify/server.py
@@ -534,9 +534,7 @@ class Watcher(object):
                 self.ui.note('%s processing %d deferred events as %d\n' %
                              (self.event_time(), self.deferred,
                               len(self.eventq)))
-            eventq = self.eventq.items()
-            eventq.sort()
-            for wpath, evts in eventq:
+            for wpath, evts in util.sort(self.eventq.items()):
                 for evt in evts:
                     self.deferred_event(wpath, evt)
             self.eventq.clear()
diff --git a/hgext/keyword.py b/hgext/keyword.py
--- a/hgext/keyword.py
+++ b/hgext/keyword.py
@@ -183,7 +183,6 @@ class kwtemplater(object):
         candidates = [f for f in files if self.iskwfile(f, ctx.flags)]
         if candidates:
             self.restrict = True # do not expand when reading
-            candidates.sort()
             action = expand and 'expanding' or 'shrinking'
             for f in candidates:
                 fp = self.repo.file(f)
@@ -382,8 +381,7 @@ def files(ui, repo, *pats, **opts):
     kwt = kwtools['templater']
     status = _status(ui, repo, kwt, opts.get('untracked'), *pats, **opts)
     modified, added, removed, deleted, unknown, ignored, clean = status
-    files = modified + added + clean + unknown
-    files.sort()
+    files = util.sort(modified + added + clean + unknown)
     wctx = repo[None]
     kwfiles = [f for f in files if kwt.iskwfile(f, wctx.flags)]
     cwd = pats and repo.getcwd() or ''
diff --git a/hgext/mq.py b/hgext/mq.py
--- a/hgext/mq.py
+++ b/hgext/mq.py
@@ -143,8 +143,7 @@ class queue:
             bad = self.check_guard(guard)
             if bad:
                 raise util.Abort(bad)
-        guards = dict.fromkeys(guards).keys()
-        guards.sort()
+        guards = util.sort(util.unique(guards))
         self.ui.debug('active guards: %s\n' % ' '.join(guards))
         self.active_guards = guards
         self.guards_dirty = True
@@ -536,8 +535,7 @@ class queue:
         return (err, n)
 
     def _clean_series(self, patches):
-        indices = [self.find_series(p) for p in patches]
-        indices.sort()
+        indices = util.sort([self.find_series(p) for p in patches])
         for i in indices[-1::-1]:
             del self.full_series[i]
         self.parse_series()
@@ -545,10 +543,10 @@ class queue:
 
     def finish(self, repo, revs):
         revs.sort()
-        firstrev = repo.changelog.rev(revlog.bin(self.applied[0].rev))
+        firstrev = repo[self.applied[0].rev].rev()
         appliedbase = 0
         patches = []
-        for rev in revs:
+        for rev in util.sort(revs):
             if rev < firstrev:
                 raise util.Abort(_('revision %d is not managed') % rev)
             base = revlog.bin(self.applied[appliedbase].rev)
@@ -1261,8 +1259,7 @@ class queue:
                                    self.guards_path)
                         and not fl.startswith('.')):
                         msng_list.append(fl)
-            msng_list.sort()
-            for x in msng_list:
+            for x in util.sort(msng_list):
                 pfx = self.ui.verbose and ('D ') or ''
                 self.ui.write("%s%s\n" % (pfx, displayname(x)))
 
diff --git a/hgext/notify.py b/hgext/notify.py
--- a/hgext/notify.py
+++ b/hgext/notify.py
@@ -156,9 +156,7 @@ class notifier(object):
             if fnmatch.fnmatch(self.repo.root, pat):
                 for user in users.split(','):
                     subs[self.fixmail(user)] = 1
-        subs = subs.keys()
-        subs.sort()
-        return subs
+        return util.sort(subs)
 
     def url(self, path=None):
         return self.ui.config('web', 'baseurl') + (path or self.root)
diff --git a/hgext/purge.py b/hgext/purge.py
--- a/hgext/purge.py
+++ b/hgext/purge.py
@@ -77,15 +77,12 @@ def purge(ui, repo, *dirs, **opts):
     match = cmdutil.match(repo, dirs, opts)
     match.dir = directories.append
     status = repo.status(match=match, ignored=opts['all'], unknown=True)
-    files = status[4] + status[5]
-    files.sort()
-    directories.sort()
 
-    for f in files:
+    for f in util.sort(status[4] + status[5]):
         ui.note(_('Removing file %s\n') % f)
         remove(os.remove, f)
 
-    for f in directories[::-1]:
+    for f in util.sort(directories)[::-1]:
         if match(f) and not os.listdir(repo.wjoin(f)):
             ui.note(_('Removing directory %s\n') % f)
             remove(os.rmdir, f)
diff --git a/hgext/transplant.py b/hgext/transplant.py
--- a/hgext/transplant.py
+++ b/hgext/transplant.py
@@ -88,9 +88,7 @@ class transplanter:
 
     def apply(self, repo, source, revmap, merges, opts={}):
         '''apply the revisions in revmap one by one in revision order'''
-        revs = revmap.keys()
-        revs.sort()
-
+        revs = util.sort(revmap)
         p1, p2 = repo.dirstate.parents()
         pulls = []
         diffopts = patch.diffopts(self.ui, opts)
@@ -310,9 +308,7 @@ class transplanter:
         if not os.path.isdir(self.path):
             os.mkdir(self.path)
         series = self.opener('series', 'w')
-        revs = revmap.keys()
-        revs.sort()
-        for rev in revs:
+        for rev in util.sort(revmap):
             series.write(revlog.hex(revmap[rev]) + '\n')
         if merges:
             series.write('# Merges\n')
@@ -572,10 +568,6 @@ def transplant(ui, repo, *revs, **opts):
         for r in merges:
             revmap[source.changelog.rev(r)] = r
 
-        revs = revmap.keys()
-        revs.sort()
-        pulls = []
-
         tp.apply(repo, source, revmap, merges, opts)
     finally:
         if bundle:
diff --git a/mercurial/changelog.py b/mercurial/changelog.py
--- a/mercurial/changelog.py
+++ b/mercurial/changelog.py
@@ -130,9 +130,7 @@ class changelog(revlog):
 
     def encode_extra(self, d):
         # keys must be sorted to produce a deterministic changelog entry
-        keys = d.keys()
-        keys.sort()
-        items = [_string_escape('%s:%s' % (k, d[k])) for k in keys]
+        items = [_string_escape('%s:%s' % (k, d[k])) for k in util.sort(d)]
         return "\0".join(items)
 
     def read(self, node):
@@ -175,7 +173,7 @@ class changelog(revlog):
         files = l[3:]
         return (manifest, user, (time, timezone), files, desc, extra)
 
-    def add(self, manifest, list, desc, transaction, p1=None, p2=None,
+    def add(self, manifest, files, desc, transaction, p1=None, p2=None,
                   user=None, date=None, extra={}):
 
         user, desc = util.fromlocal(user), util.fromlocal(desc)
@@ -189,7 +187,6 @@ class changelog(revlog):
         if extra:
             extra = self.encode_extra(extra)
             parseddate = "%s %s" % (parseddate, extra)
-        list.sort()
-        l = [hex(manifest), user, parseddate] + list + ["", desc]
+        l = [hex(manifest), user, parseddate] + util.sort(files) + ["", desc]
         text = "\n".join(l)
         return self.addrevision(text, transaction, len(self), p1, p2)
diff --git a/mercurial/cmdutil.py b/mercurial/cmdutil.py
--- a/mercurial/cmdutil.py
+++ b/mercurial/cmdutil.py
@@ -653,9 +653,7 @@ class changeset_printer(object):
             self.ui.write(_("copies:      %s\n") % ' '.join(copies))
 
         if extra and self.ui.debugflag:
-            extraitems = extra.items()
-            extraitems.sort()
-            for key, value in extraitems:
+            for key, value in util.sort(extra.items()):
                 self.ui.write(_("extra:       %s=%s\n")
                               % (key, value.encode('string_escape')))
 
@@ -799,9 +797,7 @@ class changeset_templater(changeset_prin
             return showlist('tag', self.repo.nodetags(changenode), **args)
 
         def showextras(**args):
-            extras = changes[5].items()
-            extras.sort()
-            for key, value in extras:
+            for key, value in util.sort(changes[5].items()):
                 args = args.copy()
                 args.update(dict(key=key, value=value))
                 yield self.t('extra', **args)
@@ -1129,9 +1125,7 @@ def walkchangerevs(ui, repo, pats, chang
         for i, window in increasing_windows(0, len(revs)):
             yield 'window', revs[0] < revs[-1], revs[-1]
             nrevs = [rev for rev in revs[i:i+window] if want(rev)]
-            srevs = list(nrevs)
-            srevs.sort()
-            for rev in srevs:
+            for rev in util.sort(list(nrevs)):
                 fns = fncache.get(rev)
                 if not fns:
                     def fns_generator():
@@ -1159,7 +1153,7 @@ def commit(ui, repo, commitfunc, pats, o
     m = match(repo, pats, opts)
     if pats:
         modified, added, removed = repo.status(match=m)[:3]
-        files = modified + added + removed
+        files = util.sort(modified + added + removed)
         slist = None
         for f in m.files():
             if f == '.':
@@ -1173,11 +1167,8 @@ def commit(ui, repo, commitfunc, pats, o
                     raise util.Abort(_("file %s not found!") % rel)
                 if stat.S_ISDIR(mode):
                     name = f + '/'
-                    if slist is None:
-                        slist = list(files)
-                        slist.sort()
-                    i = bisect.bisect(slist, name)
-                    if i >= len(slist) or not slist[i].startswith(name):
+                    i = bisect.bisect(files, name)
+                    if i >= len(files) or not files[i].startswith(name):
                         raise util.Abort(_("no match under directory %s!")
                                          % rel)
                 elif not (stat.S_ISREG(mode) or stat.S_ISLNK(mode)):
diff --git a/mercurial/commands.py b/mercurial/commands.py
--- a/mercurial/commands.py
+++ b/mercurial/commands.py
@@ -380,9 +380,8 @@ def branches(ui, repo, active=False):
     hexfunc = ui.debugflag and hex or short
     activebranches = [util.tolocal(repo[n].branch())
                             for n in repo.heads()]
-    branches = [(tag in activebranches, repo.changelog.rev(node), tag)
-                            for tag, node in repo.branchtags().items()]
-    branches.sort()
+    branches = util.sort([(tag in activebranches, repo.changelog.rev(node), tag)
+                          for tag, node in repo.branchtags().items()])
     branches.reverse()
 
     for isactive, node, tag in branches:
@@ -635,9 +634,7 @@ def debugcomplete(ui, cmd='', **opts):
         ui.write("%s\n" % "\n".join(options))
         return
 
-    clist = cmdutil.findpossible(ui, cmd, table).keys()
-    clist.sort()
-    ui.write("%s\n" % "\n".join(clist))
+    ui.write("%s\n" % "\n".join(util.sort(cmdutil.findpossible(ui, cmd, table))))
 
 def debugfsinfo(ui, path = "."):
     file('.debugfsinfo', 'w').write('')
@@ -727,11 +724,9 @@ def debugsetparents(ui, repo, rev1, rev2
 
 def debugstate(ui, repo, nodates=None):
     """show the contents of the current dirstate"""
-    k = repo.dirstate._map.items()
-    k.sort()
     timestr = ""
     showdate = not nodates
-    for file_, ent in k:
+    for file_, ent in util.sort(repo.dirstate._map.items()):
         if showdate:
             if ent[3] == -1:
                 # Pad or slice to locale representation
@@ -1142,9 +1137,7 @@ def grep(ui, repo, pattern, *pats, **opt
                 except revlog.LookupError:
                     pass
         elif st == 'iter':
-            states = matches[rev].items()
-            states.sort()
-            for fn, m in states:
+            for fn, m in util.sort(matches[rev].items()):
                 copy = copies.get(rev, {}).get(fn)
                 if fn in skip:
                     if copy:
@@ -1162,9 +1155,7 @@ def grep(ui, repo, pattern, *pats, **opt
                     fstate[copy] = m
                 prev[fn] = rev
 
-    fstate = fstate.items()
-    fstate.sort()
-    for fn, state in fstate:
+    for fn, state in util.sort(fstate.items()):
         if fn in skip:
             continue
         if fn not in copies.get(prev[fn], {}):
@@ -1304,8 +1295,7 @@ def help_(ui, name=None, with_version=Fa
             return
 
         ui.status(header)
-        fns = h.keys()
-        fns.sort()
+        fns = util.sort(h)
         m = max(map(len, fns))
         for f in fns:
             if ui.verbose:
@@ -2215,9 +2205,7 @@ def remove(ui, repo, *pats, **opts):
         warn(modified, _('is modified'))
         warn(added, _('has been marked for add'))
 
-    files = remove + forget
-    files.sort()
-    for f in files:
+    for f in util.sort(remove + forget):
         if ui.verbose or not m.exact(f):
             ui.status(_('removing %s\n') % m.rel(f))
 
@@ -2401,10 +2389,7 @@ def revert(ui, repo, *pats, **opts):
             (deleted, revert, remove, False, False),
             )
 
-        entries = names.items()
-        entries.sort()
-
-        for abs, (rel, exact) in entries:
+        for abs, (rel, exact) in util.sort(names.items()):
             mfentry = mf.get(abs)
             target = repo.wjoin(abs)
             def handle(xlist, dobackup):
diff --git a/mercurial/context.py b/mercurial/context.py
--- a/mercurial/context.py
+++ b/mercurial/context.py
@@ -71,9 +71,7 @@ class changectx(object):
         return self.filectx(key)
 
     def __iter__(self):
-        a = self._manifest.keys()
-        a.sort()
-        for f in a:
+        for f in util.sort(self._manifest):
             yield f
 
     def changeset(self): return self._changeset
@@ -134,10 +132,7 @@ class changectx(object):
     def filectxs(self):
         """generate a file context for each file in this changeset's
            manifest"""
-        mf = self.manifest()
-        m = mf.keys()
-        m.sort()
-        for f in m:
+        for f in util.sort(mf):
             yield self.filectx(f, fileid=mf[f])
 
     def ancestor(self, c2):
@@ -383,12 +378,11 @@ class filectx(object):
         # sort by revision (per file) which is a topological order
         visit = []
         for f in files:
-            fn = [(n.rev(), n) for n in needed.keys() if n._path == f]
+            fn = [(n.rev(), n) for n in needed if n._path == f]
             visit.extend(fn)
-        visit.sort()
+
         hist = {}
-
-        for r, f in visit:
+        for r, f in util.sort(visit):
             curr = decorate(f.data(), f)
             for p in parents(f):
                 if p != nullid:
@@ -530,9 +524,7 @@ class workingctx(changectx):
     def date(self): return self._date
     def description(self): return self._text
     def files(self):
-        f = self.modified() + self.added() + self.removed()
-        f.sort()
-        return f
+        return util.sort(self._status[0] + self._status[1] + self._status[2])
 
     def modified(self): return self._status[0]
     def added(self): return self._status[1]
@@ -688,8 +680,7 @@ class memctx(object):
         parents = [(p or nullid) for p in parents]
         p1, p2 = parents
         self._parents = [changectx(self._repo, p) for p in (p1, p2)]
-        files = list(files)
-        files.sort()
+        files = util.sort(list(files))
         self._status = [files, [], [], [], []]
         self._filectxfn = filectxfn
 
diff --git a/mercurial/copies.py b/mercurial/copies.py
--- a/mercurial/copies.py
+++ b/mercurial/copies.py
@@ -11,9 +11,7 @@ import util, heapq
 
 def _nonoverlap(d1, d2, d3):
     "Return list of elements in d1 not in d2 or d3"
-    l = [d for d in d1 if d not in d3 and d not in d2]
-    l.sort()
-    return l
+    return util.sort([d for d in d1 if d not in d3 and d not in d2])
 
 def _dirname(f):
     s = f.rfind("/")
@@ -49,9 +47,7 @@ def _findoldnames(fctx, limit):
         visit += [(p, depth - 1) for p in fc.parents()]
 
     # return old names sorted by depth
-    old = old.values()
-    old.sort()
-    return [o[1] for o in old]
+    return [o[1] for o in util.sort(old.values())]
 
 def _findlimit(repo, a, b):
     "find the earliest revision that's an ancestor of a or b but not both"
diff --git a/mercurial/dirstate.py b/mercurial/dirstate.py
--- a/mercurial/dirstate.py
+++ b/mercurial/dirstate.py
@@ -153,9 +153,7 @@ class dirstate(object):
         return key in self._map
 
     def __iter__(self):
-        a = self._map.keys()
-        a.sort()
-        for x in a:
+        for x in util.sort(self._map):
             yield x
 
     def parents(self):
@@ -436,8 +434,7 @@ class dirstate(object):
         if not unknown:
             return ret
 
-        b = self._map.keys()
-        b.sort()
+        b = util.sort(self._map)
         blen = len(b)
 
         for x in unknown:
@@ -578,12 +575,10 @@ class dirstate(object):
                             add((nn, 'f', st))
                         elif np in dc:
                             add((nn, 'm', st))
-            found.sort()
-            return found
+            return util.sort(found)
 
         # step one, find all files that match our criteria
-        files.sort()
-        for ff in files:
+        for ff in util.sort(files):
             nf = normpath(ff)
             nn = self.normalize(nf)
             f = _join(ff)
@@ -617,9 +612,7 @@ class dirstate(object):
 
         # step two run through anything left in the dc hash and yield
         # if we haven't already seen it
-        ks = dc.keys()
-        ks.sort()
-        for k in ks:
+        for k in util.sort(dc):
             if k in known:
                 continue
             known[k] = 1
diff --git a/mercurial/filemerge.py b/mercurial/filemerge.py
--- a/mercurial/filemerge.py
+++ b/mercurial/filemerge.py
@@ -63,8 +63,7 @@ def _picktool(repo, ui, path, binary, sy
         if t not in tools:
             tools[t] = int(_toolstr(ui, t, "priority", "0"))
     names = tools.keys()
-    tools = [(-p,t) for t,p in tools.items()]
-    tools.sort()
+    tools = util.sort([(-p,t) for t,p in tools.items()])
     uimerge = ui.config("ui", "merge")
     if uimerge:
         if uimerge not in names:
diff --git a/mercurial/hbisect.py b/mercurial/hbisect.py
--- a/mercurial/hbisect.py
+++ b/mercurial/hbisect.py
@@ -60,7 +60,6 @@ def bisect(changelog, state):
                         children[prev] = [rev]
                         visit.append(prev)
 
-    candidates.sort()
     # have we narrowed it down to one entry?
     tot = len(candidates)
     if tot == 1:
@@ -71,7 +70,7 @@ def bisect(changelog, state):
     best_rev = None
     best_len = -1
     poison = {}
-    for rev in candidates:
+    for rev in util.sort(candidates):
         if rev in poison:
             for c in children.get(rev, []):
                 poison[c] = True # poison children
diff --git a/mercurial/hgweb/hgwebdir_mod.py b/mercurial/hgweb/hgwebdir_mod.py
--- a/mercurial/hgweb/hgwebdir_mod.py
+++ b/mercurial/hgweb/hgwebdir_mod.py
@@ -19,8 +19,8 @@ from request import wsgirequest
 class hgwebdir(object):
     def __init__(self, config, parentui=None):
         def cleannames(items):
-            return [(util.pconvert(name).strip('/'), path)
-                    for name, path in items]
+            return util.sort([(util.pconvert(name).strip('/'), path)
+                              for name, path in items])
 
         self.parentui = parentui or ui.ui(report_untrusted=False,
                                           interactive = False)
@@ -34,7 +34,6 @@ class hgwebdir(object):
             self.repos_sorted = ('', False)
         elif isinstance(config, dict):
             self.repos = cleannames(config.items())
-            self.repos.sort()
         else:
             if isinstance(config, util.configparser):
                 cp = config
diff --git a/mercurial/hgweb/webcommands.py b/mercurial/hgweb/webcommands.py
--- a/mercurial/hgweb/webcommands.py
+++ b/mercurial/hgweb/webcommands.py
@@ -13,7 +13,7 @@ from mercurial.util import binary, dates
 from mercurial.repo import RepoError
 from common import paritygen, staticfile, get_contact, ErrorResponse
 from common import HTTP_OK, HTTP_NOT_FOUND
-from mercurial import graphmod
+from mercurial import graphmod, util
 
 # __all__ is populated with the allowed commands. Be sure to add to it if
 # you're adding a new command, or the new command won't work.
@@ -288,9 +288,7 @@ def manifest(web, req, tmpl):
         raise ErrorResponse(HTTP_NOT_FOUND, 'path not found: ' + path)
 
     def filelist(**map):
-        fl = files.keys()
-        fl.sort()
-        for f in fl:
+        for f in util.sort(files):
             full, fnode = files[f]
             if not fnode:
                 continue
@@ -304,9 +302,7 @@ def manifest(web, req, tmpl):
                    "permissions": mf.flags(full)}
 
     def dirlist(**map):
-        fl = files.keys()
-        fl.sort()
-        for f in fl:
+        for f in util.sort(files):
             full, fnode = files[f]
             if fnode:
                 continue
@@ -378,9 +374,7 @@ def summary(web, req, tmpl):
 
         b = web.repo.branchtags()
         l = [(-web.repo.changelog.rev(n), n, t) for t, n in b.items()]
-        l.sort()
-
-        for r,n,t in l:
+        for r,n,t in util.sort(l):
             yield {'parity': parity.next(),
                    'branch': t,
                    'node': hex(n),
diff --git a/mercurial/hook.py b/mercurial/hook.py
--- a/mercurial/hook.py
+++ b/mercurial/hook.py
@@ -96,10 +96,9 @@ def hook(ui, repo, name, throw=False, **
         oldstdout = os.dup(sys.__stdout__.fileno())
         os.dup2(sys.__stderr__.fileno(), sys.__stdout__.fileno())
 
-    hooks = [(hname, cmd) for hname, cmd in ui.configitems("hooks")
-             if hname.split(".", 1)[0] == name and cmd]
-    hooks.sort()
-    for hname, cmd in hooks:
+    for hname, cmd in util.sort(ui.configitems('hooks')):
+        if hname.split('.')[0] != name or not cmd:
+            continue
         if callable(cmd):
             r = _pythonhook(ui, repo, name, hname, cmd, args, throw) or r
         elif cmd.startswith('python:'):
diff --git a/mercurial/localrepo.py b/mercurial/localrepo.py
--- a/mercurial/localrepo.py
+++ b/mercurial/localrepo.py
@@ -366,8 +366,7 @@ class localrepository(repo.repository):
             except:
                 r = -2 # sort to the beginning of the list if unknown
             l.append((r, t, n))
-        l.sort()
-        return [(t, n) for r, t, n in l]
+        return [(t, n) for r, t, n in util.sort(l)]
 
     def nodetags(self, node):
         '''return the tags associated with a node'''
@@ -811,7 +810,7 @@ class localrepository(repo.repository):
         tr = None
         valid = 0 # don't save the dirstate if this isn't set
         try:
-            commit = wctx.modified() + wctx.added()
+            commit = util.sort(wctx.modified() + wctx.added())
             remove = wctx.removed()
             extra = wctx.extra().copy()
             branchname = extra['branch']
@@ -844,7 +843,6 @@ class localrepository(repo.repository):
             new = {}
             changed = []
             linkrev = len(self)
-            commit.sort()
             for f in commit:
                 self.ui.note(f + "\n")
                 try:
@@ -871,10 +869,9 @@ class localrepository(repo.repository):
 
             # update manifest
             m1.update(new)
-            remove.sort()
             removed = []
 
-            for f in remove:
+            for f in util.sort(remove):
                 if f in m1:
                     del m1[f]
                     removed.append(f)
@@ -950,10 +947,7 @@ class localrepository(repo.repository):
             # for dirstate.walk, files=['.'] means "walk the whole tree".
             # follow that here, too
             fdict.pop('.', None)
-            mdict = self.manifest.read(self.changelog.read(node)[0])
-            mfiles = mdict.keys()
-            mfiles.sort()
-            for fn in mfiles:
+            for fn in self[node]:
                 for ffn in fdict:
                     # match if the file is the exact name or a directory
                     if ffn == fn or fn.startswith("%s/" % ffn):
@@ -961,9 +955,7 @@ class localrepository(repo.repository):
                         break
                 if match(fn):
                     yield fn
-            ffiles = fdict.keys()
-            ffiles.sort()
-            for fn in ffiles:
+            for fn in util.sort(fdict):
                 if match.bad(fn, 'No such file in rev ' + short(node)) \
                         and match(fn):
                     yield fn
@@ -1065,10 +1057,8 @@ class localrepository(repo.repository):
 
             # make sure to sort the files so we talk to the disk in a
             # reasonable order
-            mf2keys = mf2.keys()
-            mf2keys.sort()
             getnode = lambda fn: mf1.get(fn, nullid)
-            for fn in mf2keys:
+            for fn in util.sort(mf2):
                 if fn in mf1:
                     if (mf1.flags(fn) != mf2.flags(fn) or
                         (mf1[fn] != mf2[fn] and
@@ -1190,8 +1180,7 @@ class localrepository(repo.repository):
         heads = self.changelog.heads(start)
         # sort the output in rev descending order
         heads = [(-self.changelog.rev(h), h) for h in heads]
-        heads.sort()
-        return [n for (r, n) in heads]
+        return [n for (r, n) in util.sort(heads)]
 
     def branchheads(self, branch=None, start=None):
         if branch is None:
@@ -1843,10 +1832,8 @@ class localrepository(repo.repository):
                     add_extra_nodes(fname,
                                     msng_filenode_set.setdefault(fname, {}))
                     changedfiles[fname] = 1
-            changedfiles = changedfiles.keys()
-            changedfiles.sort()
             # Go through all our files in order sorted by name.
-            for fname in changedfiles:
+            for fname in util.sort(changedfiles):
                 filerevlog = self.file(fname)
                 if not len(filerevlog):
                     raise util.Abort(_("empty or missing revlog for %s") % fname)
@@ -1924,15 +1911,13 @@ class localrepository(repo.repository):
             for chnk in cl.group(nodes, identity,
                                  changed_file_collector(changedfiles)):
                 yield chnk
-            changedfiles = changedfiles.keys()
-            changedfiles.sort()
 
             mnfst = self.manifest
             nodeiter = gennodelst(mnfst)
             for chnk in mnfst.group(nodeiter, lookuprevlink_func(mnfst)):
                 yield chnk
 
-            for fname in changedfiles:
+            for fname in util.sort(changedfiles):
                 filerevlog = self.file(fname)
                 if not len(filerevlog):
                     raise util.Abort(_("empty or missing revlog for %s") % fname)
diff --git a/mercurial/manifest.py b/mercurial/manifest.py
--- a/mercurial/manifest.py
+++ b/mercurial/manifest.py
@@ -8,7 +8,7 @@
 from node import bin, hex, nullid
 from revlog import revlog, RevlogError
 from i18n import _
-import array, struct, mdiff, parsers
+import array, struct, mdiff, parsers, util
 
 class manifestdict(dict):
     def __init__(self, mapping=None, flags=None):
@@ -126,9 +126,7 @@ class manifest(revlog):
         # if we're using the listcache, make sure it is valid and
         # parented by the same node we're diffing against
         if not (changed and self.listcache and p1 and self.mapcache[0] == p1):
-            files = map.keys()
-            files.sort()
-
+            files = util.sort(map)
             for f in files:
                 checkforbidden(f)
 
diff --git a/mercurial/merge.py b/mercurial/merge.py
--- a/mercurial/merge.py
+++ b/mercurial/merge.py
@@ -262,11 +262,10 @@ def applyupdates(repo, action, wctx, mct
     "apply the merge action list to the working directory"
 
     updated, merged, removed, unresolved = 0, 0, 0, 0
-    action.sort()
-
     ms = mergestate(repo)
     ms.reset(wctx.parents()[0].node())
     moves = []
+    action.sort()
 
     # prescan for merges
     for a in action:
diff --git a/mercurial/patch.py b/mercurial/patch.py
--- a/mercurial/patch.py
+++ b/mercurial/patch.py
@@ -1094,8 +1094,7 @@ def updatedir(ui, repo, patches):
         repo.copy(src, dst)
     removes = removes.keys()
     if removes:
-        removes.sort()
-        repo.remove(removes, True)
+        repo.remove(util.sort(removes), True)
     for f in patches:
         ctype, gp = patches[f]
         if gp and gp.mode:
@@ -1113,9 +1112,7 @@ def updatedir(ui, repo, patches):
     cmdutil.addremove(repo, cfiles)
     files = patches.keys()
     files.extend([r for r in removes if r not in files])
-    files.sort()
-
-    return files
+    return util.sort(files)
 
 def b85diff(to, tn):
     '''print base85-encoded binary diff'''
@@ -1208,13 +1205,10 @@ def diff(repo, node1=None, node2=None, m
         for k, v in copy.items():
             copy[v] = k
 
-    all = modified + added + removed
-    all.sort()
     gone = {}
-
     gitmode = {'l': '120000', 'x': '100755', '': '100644'}
 
-    for f in all:
+    for f in util.sort(modified + added + removed):
         to = None
         tn = None
         dodiff = True
diff --git a/mercurial/streamclone.py b/mercurial/streamclone.py
--- a/mercurial/streamclone.py
+++ b/mercurial/streamclone.py
@@ -34,8 +34,7 @@ def walkrepo(root):
     for x in walk(os.path.join(root, 'data'), True):
         yield x
     # write manifest before changelog
-    meta = list(walk(root, False))
-    meta.sort()
+    meta = util.sort(walk(root, False))
     meta.reverse()
     for x in meta:
         yield x
diff --git a/mercurial/ui.py b/mercurial/ui.py
--- a/mercurial/ui.py
+++ b/mercurial/ui.py
@@ -312,15 +312,11 @@ class ui(object):
         items = self._configitems(section, untrusted=untrusted, abort=True)
         if self.debugflag and not untrusted and self.ucdata:
             uitems = self._configitems(section, untrusted=True, abort=False)
-            keys = uitems.keys()
-            keys.sort()
-            for k in keys:
+            for k in util.sort(uitems):
                 if uitems[k] != items.get(k):
                     self.warn(_("Ignoring untrusted configuration option "
                                 "%s.%s = %s\n") % (section, k, uitems[k]))
-        x = items.items()
-        x.sort()
-        return x
+        return util.sort(items.items())
 
     def walkconfig(self, untrusted=False):
         cdata = self._get_cdata(untrusted)
diff --git a/mercurial/util.py b/mercurial/util.py
--- a/mercurial/util.py
+++ b/mercurial/util.py
@@ -252,6 +252,12 @@ def unique(g):
     """return the uniq elements of iterable g"""
     return dict.fromkeys(g).keys()
 
+def sort(l):
+    if not isinstance(l, list):
+        l = list(l)
+    l.sort()
+    return l
+
 class Abort(Exception):
     """Raised if a command needs to print an error and exit."""
 
diff --git a/mercurial/verify.py b/mercurial/verify.py
--- a/mercurial/verify.py
+++ b/mercurial/verify.py
@@ -7,7 +7,7 @@
 
 from node import nullid, short
 from i18n import _
-import revlog
+import revlog, util
 
 def verify(repo):
     lock = repo.lock()
@@ -139,38 +139,26 @@ def _verify(repo):
     ui.status(_("crosschecking files in changesets and manifests\n"))
 
     if havemf:
-        nm = []
-        for m in mflinkrevs:
-            for c in mflinkrevs[m]:
-                nm.append((c, m))
-        nm.sort()
-        for c, m in nm:
+        for c, m in util.sort([(c, m) for m in mflinkrevs for c in mflinkrevs[m]]):
             err(c, _("changeset refers to unknown manifest %s") % short(m))
-        del mflinkrevs, nm
+        del mflinkrevs
 
-        fl = filelinkrevs.keys()
-        fl.sort()
-        for f in fl:
+        for f in util.sort(filelinkrevs):
             if f not in filenodes:
                 lr = filelinkrevs[f][0]
                 err(lr, _("in changeset but not in manifest"), f)
-        del fl
 
     if havecl:
-        fl = filenodes.keys()
-        fl.sort()
-        for f in fl:
+        for f in util.sort(filenodes):
             if f not in filelinkrevs:
                 try:
                     lr = min([repo.file(f).linkrev(n) for n in filenodes[f]])
                 except:
                     lr = None
                 err(lr, _("in manifest but not in changeset"), f)
-        del fl
 
     ui.status(_("checking files\n"))
-    files = dict.fromkeys(filenodes.keys() + filelinkrevs.keys()).keys()
-    files.sort()
+    files = util.sort(util.unique(filenodes.keys() + filelinkrevs.keys()))
     for f in files:
         fl = repo.file(f)
         checklog(fl, f)
@@ -214,8 +202,7 @@ def _verify(repo):
         # cross-check
         if f in filenodes:
             fns = [(mf.linkrev(l), n) for n,l in filenodes[f].items()]
-            fns.sort()
-            for lr, node in fns:
+            for lr, node in util.sort(fns):
                 err(lr, _("%s in manifests not found") % short(node), f)
 
     ui.status(_("%d files, %d changesets, %d total revisions\n") %