Bruno Haible wrote:
Jim Meyering wrote:
+ if (nitems > _FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD
+ && !sp->fts_compar
+ && dirent_inode_sort_may_be_useful (sp)) {
+ sp->fts_compar = fts_compare_ino;
+ head = fts_sort (sp, head, nitems);
+ sp->fts_compar = NULL;
+ }
This uses fts_sort, which uses qsort, which is O(n^2) in the worst case.
(Even the implementation in glibc can be O(n^2), if it guesses that mergesort
takes too much memory.)
Couldn't this be avoided by using Paul's mpsort module, and changing fts_sort
to allocate 50% more room, as scratch space for mpsort?
You're talking about inode numbers (i.e. fixed-sized keys), yes? Could
this be a case for a radix sort?
--
Matthew
Please do not quote my e-mail address unobfuscated in message bodies.
--
"Who wants to sing?" -- Orcs (Warcraft II)