From nobody Thu Apr 20 06:32:54 2023 X-Original-To: dev-commits-src-main@mlmmj.nyi.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mlmmj.nyi.freebsd.org (Postfix) with ESMTP id 4Q27Bh4NGcz46NGR; Thu, 20 Apr 2023 06:33:00 +0000 (UTC) (envelope-from hselasky@freebsd.org) Received: from mail.turbocat.net (turbocat.net [IPv6:2a01:4f8:c17:6c4b::2]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (Client did not present a certificate) by mx1.freebsd.org (Postfix) with ESMTPS id 4Q27Bg5GwNz3JTx; Thu, 20 Apr 2023 06:32:59 +0000 (UTC) (envelope-from hselasky@freebsd.org) Authentication-Results: mx1.freebsd.org; none Received: from [10.36.2.154] (unknown [46.212.121.255]) (using TLSv1.3 with cipher TLS_AES_128_GCM_SHA256 (128/128 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits)) (No client certificate requested) by mail.turbocat.net (Postfix) with ESMTPSA id D2B1F2603CF; Thu, 20 Apr 2023 08:32:53 +0200 (CEST) Message-ID: <1ce00b7b-e34b-a91b-59ef-c3ee9683c4a0@freebsd.org> Date: Thu, 20 Apr 2023 08:32:54 +0200 List-Id: Commit messages for the main branch of the src repository List-Archive: https://lists.freebsd.org/archives/dev-commits-src-main List-Help: List-Post: List-Subscribe: List-Unsubscribe: Sender: owner-dev-commits-src-main@freebsd.org X-BeenThere: dev-commits-src-main@freebsd.org MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; FreeBSD amd64; rv:102.0) Gecko/20100101 Thunderbird/102.10.0 Subject: Re: git: 8dcf3a82c54c - main - libc: Implement bsort(3) a bitonic type of sorting algorithm. Content-Language: en-US To: Colin Percival , Jessica Clarke Cc: Brooks Davis , src-committers , dev-commits-src-all@freebsd.org, dev-commits-src-main@freebsd.org References: <202304191206.33JC6Qcp062380@gitrepo.freebsd.org> <3B5734C4-8630-4CD5-BA8D-DE33899161F1@freebsd.org> <2840BE79-CC25-427A-A5E9-476A38E749E3@freebsd.org> <42d63675-9b1f-70dc-a1da-fef3d43790fd@freebsd.org> <010001879ba20fa7-95ae06cc-e046-4f59-a9b7-5e2cd389d101-000000@email.amazonses.com> From: Hans Petter Selasky In-Reply-To: <010001879ba20fa7-95ae06cc-e046-4f59-a9b7-5e2cd389d101-000000@email.amazonses.com> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit X-Rspamd-Queue-Id: 4Q27Bg5GwNz3JTx X-Spamd-Bar: ---- X-Spamd-Result: default: False [-4.00 / 15.00]; REPLY(-4.00)[]; ASN(0.00)[asn:24940, ipnet:2a01:4f8::/32, country:DE] X-Rspamd-Pre-Result: action=no action; module=replies; Message is reply to one we originated X-ThisMailContainsUnwantedMimeParts: N On 4/20/23 00:28, Colin Percival wrote: > > Quicksort with cryptographically randomized pivot selection is O(N^2) worst > case but O(N log N) average-case-for-worst-case-inputs which is good enough > for most purposes. > > Quicksort with in-place median-of-medians pivot selection is O(N log N) > worst > case. > > Both of them can be easily implemented with O(log N) extra space (for > the call > stack), and with O(1) extra space if you're insane enough to care. Yes, I know there are different ways to mitigate O(N^2) behaviour, but there is not yet after xxx years of research a way to fully mitigate that behaviour. What I think, there should be some statistics done in our qsort() when it goes to O(N^2), and then it could fallback to bsort() for example, to avoid issues with malloc(). Or maybe one round of bsort() is enough to make qsort() do its thing right. I want to investigate that. Like a hybrid. --HPS