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? Bruno