----- On May 3, 2022, at 1:15 PM, Mihai Moldovan io...@ionic.de wrote: > Just a nit, feel free to ignore it... > > > * On 5/3/22 4:42 PM, Mathieu Desnoyers wrote: >> How does the following paragraph sound ? >> >> ^^^^^^^^ >> Here is the improved algorithm proposed: >> >> - Prepare a list with all the relevant information for ordering by a single >> sort(1) execution. This is done by renaming ".old" suffixes by " 1" and >> by suffixing all other files with " 2", thus making sure the ".old" entries >> will follow the non-old entries in reverse-sorted-order. >> - Call version_reverse_sort on the list (sort -r -V): A single execution of >> sort(1) will reverse-sort the list in O(n*log(n)) with a merge sort. > > This is correct for GNU coreutils's sort, but nothing (I'm mostly thinking of > SUS/POSIX here) mandates that the sort utility must either use merge sort or > have O(n*log(n)) time complexity. > > Given that you're using version sort, which is a GNU extension, it probably > can't be anything than GNU sort anyway, though, so the point still holds by > implicity.
I'm using the same sort already used in version_sort(). It uses sort -V if available, but there is a fallback to sort if -V is not available. Therefore, nothing implies a version sort, so nothing implies a GNU extension. So your point about other sort not necessarily being O(nlog(n)) merge sort is valid. I will remove this statement from the next patch version commit message. Thanks, Mathieu -- Mathieu Desnoyers EfficiOS Inc. http://www.efficios.com _______________________________________________ Grub-devel mailing list Grub-devel@gnu.org https://lists.gnu.org/mailman/listinfo/grub-devel
