Bruno Haible <[EMAIL PROTECTED]> 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?
Good point! That would make a fine improvement, as a separate patch. The new use of qsort in the code I've just proposed for rm would benefit from the same treatment.