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)
