From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on inbox.vuxu.org X-Spam-Level: X-Spam-Status: No, score=-1.0 required=5.0 tests=MAILING_LIST_MULTI, RCVD_IN_MSPIKE_H2 autolearn=ham autolearn_force=no version=3.4.4 Received: (qmail 27971 invoked from network); 3 Feb 2023 08:03:21 -0000 Received: from second.openwall.net (193.110.157.125) by inbox.vuxu.org with ESMTPUTF8; 3 Feb 2023 08:03:21 -0000 Received: (qmail 22040 invoked by uid 550); 3 Feb 2023 08:03:17 -0000 Mailing-List: contact musl-help@lists.openwall.com; run by ezmlm Precedence: bulk List-Post: List-Help: List-Unsubscribe: List-Subscribe: List-ID: Reply-To: musl@lists.openwall.com Received: (qmail 22002 invoked from network); 3 Feb 2023 08:03:16 -0000 DKIM-Filter: OpenDKIM Filter v2.11.0 mail.ispras.ru 8349240737AF Date: Fri, 3 Feb 2023 11:03:03 +0300 (MSK) From: Alexander Monakov To: musl@lists.openwall.com In-Reply-To: <5856a8f9.1e21.18615ba5922.Coremail.00107082@163.com> Message-ID: <841ab767-8f7c-4a4a-23ed-95901528a1b6@ispras.ru> References: <4d290220.36d6.1860222ca46.Coremail.00107082@163.com> <20230201180115.GB2626@voyager> <6b7dbb13.ce7.1860fe5f0c6.Coremail.00107082@163.com> <5856a8f9.1e21.18615ba5922.Coremail.00107082@163.com> MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Subject: Re: [musl] Re:[musl] Re:Re: [musl] Re:Re: [musl] 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'. Alexander