[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [PATCH] grub-mkconfig linux: Fix quadratic algorithm for sorting men

From: Mihai Moldovan
Subject: Re: [PATCH] grub-mkconfig linux: Fix quadratic algorithm for sorting menu items
Date: Tue, 3 May 2022 19:15:47 +0200
User-agent: Mozilla/5.0 (X11; Linux x86_64; rv:78.0) Gecko/20100101 Thunderbird/78.13.0

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

However, this also means that you're adding a hidden dependency upon GNU
coreutils sort here, which will hit systems traditionally not using the GNU
userland by default, most prominently BSDs (which, I might add, seem not to use
GRUB by default and generally either discourage it or have thrown it out of
their package management systems).


Attachment: OpenPGP_signature
Description: OpenPGP digital signature

reply via email to

[Prev in Thread] Current Thread [Next in Thread]