From nobody Wed Apr 19 22:28:22 2023 X-Original-To: dev-commits-src-all@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 4Q1wRW3kWkz45JtP for ; Wed, 19 Apr 2023 22:28:23 +0000 (UTC) (envelope-from 010001879ba20fa7-95ae06cc-e046-4f59-a9b7-5e2cd389d101-000000@amazonses.com) Received: from a8-237.smtp-out.amazonses.com (a8-237.smtp-out.amazonses.com [54.240.8.237]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-SHA256 (128/128 bits)) (Client did not present a certificate) by mx1.freebsd.org (Postfix) with ESMTPS id 4Q1wRW1dWDz3CVp for ; Wed, 19 Apr 2023 22:28:23 +0000 (UTC) (envelope-from 010001879ba20fa7-95ae06cc-e046-4f59-a9b7-5e2cd389d101-000000@amazonses.com) Authentication-Results: mx1.freebsd.org; none DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/simple; s=ae7m2yrxjw65l2cqdpjxuucyrvy564tn; d=tarsnap.com; t=1681943302; h=Message-ID:Date:MIME-Version:Subject:To:Cc:References:From:In-Reply-To:Content-Type:Content-Transfer-Encoding; bh=mA6LrvbdJieHXNqm2q1T732F2g32oolmocP2deHc8/s=; b=anufIuBsam7seUYpJWYzm0jQm+EqdQhGBOu/upyHK2nazPqll9Qs9TxZORagT3hW +dDvYTgnf5GMwtWBjE5Hr/BRtS1z7JnU9cuuD+IKiESoahElrNZzrrKIoNPim7wMw5V m37Yg2lqJXgEAqwQTi3YuywR3Ne69+zHusacM/oE= DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/simple; s=224i4yxa5dv7c2xz3womw6peuasteono; d=amazonses.com; t=1681943302; h=Message-ID:Date:MIME-Version:Subject:To:Cc:References:From:In-Reply-To:Content-Type:Content-Transfer-Encoding:Feedback-ID; bh=mA6LrvbdJieHXNqm2q1T732F2g32oolmocP2deHc8/s=; b=aETJeiHDj5X6OvGaOkMX6gN5+kpbhBuVZo76I+iqn+KerAEruwEY2/PmUNE8pP+K jLEk9cAHkV0+y7mWRDo2oXK33uOtUeax0FKiRHMSTVhRQuC7Tm6NjYf951VsB4BUukQ Y5nEqq4qZxu5rZxDqznwfzeXaps3zMWjN0NCeHTM= Message-ID: <010001879ba20fa7-95ae06cc-e046-4f59-a9b7-5e2cd389d101-000000@email.amazonses.com> Date: Wed, 19 Apr 2023 22:28:22 +0000 List-Id: Commit messages for all branches of the src repository List-Archive: https://lists.freebsd.org/archives/dev-commits-src-all List-Help: List-Post: List-Subscribe: List-Unsubscribe: Sender: owner-dev-commits-src-all@freebsd.org X-BeenThere: dev-commits-src-all@freebsd.org MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; FreeBSD amd64; rv:102.0) Gecko/20100101 Thunderbird/102.9.0 Subject: Re: git: 8dcf3a82c54c - main - libc: Implement bsort(3) a bitonic type of sorting algorithm. Content-Language: en-US To: Hans Petter Selasky , 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> From: Colin Percival In-Reply-To: <42d63675-9b1f-70dc-a1da-fef3d43790fd@freebsd.org> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Feedback-ID: 1.us-east-1.Lv9FVjaNvvR5llaqfLoOVbo2VxOELl7cjN0AOyXnPlk=:AmazonSES X-SES-Outgoing: 2023.04.19-54.240.8.237 X-Rspamd-Queue-Id: 4Q1wRW1dWDz3CVp X-Spamd-Bar: ---- X-Spamd-Result: default: False [-4.00 / 15.00]; REPLY(-4.00)[]; ASN(0.00)[asn:14618, ipnet:54.240.8.0/21, country:US] X-Rspamd-Pre-Result: action=no action; module=replies; Message is reply to one we originated X-ThisMailContainsUnwantedMimeParts: N On 4/19/23 14:41, Hans Petter Selasky wrote: > On 4/19/23 22:17, Jessica Clarke wrote: >> pdqsort is n log n time, in-place and doesn’t allocate, and is used, >> for example, for Rust’s standard sort_unstable. > > Like many many people have tried over the years, to improve the belated > QuickSort (*) algorithm since it was invented, by catching bad behaviour and > then fallback to other algorithms, pdqsort() is not a solution! > > Yes, it is probably "N log N" time, but if you read the code carefully, it > falls back to heapsort(), which indeed uses malloc(), which is exactly my > point, that I want to avoid. > > Please come forward with a "N log N" time algorithm which is malloc() and > alloca() free, and then we'll talk! 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. -- Colin Percival FreeBSD Deputy Release Engineer & EC2 platform maintainer Founder, Tarsnap | www.tarsnap.com | Online backups for the truly paranoid