Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Fri, 3 Feb 2023 11:03:03 +0300 (MSK)
From: Alexander Monakov <>
Subject: Re: Re:Re:Re: Re:Re: qsort

On Fri, 3 Feb 2023, David Wang wrote:

> I think I was not reading the mail carefully enough,  and did not notice the
> O(1) "in place" space complexity.

It's not correct to claim that musl smoothsort improves on qsort by
having O(1) space complexity rather than O(log n). The storage for
Leonardo numbers in musl smoothsort grows as O(log n) as well, musl
just allocates enough for the maximum possible 'n'.


Powered by blists - more mailing lists

Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.