From nobody Wed Apr 19 22:28:22 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 4Q1wRW3vPDz45K7r for ; Wed, 19 Apr 2023 22:28:23 +0000 (UTC) (envelope-from 010001879ba20fc8-f6f0ee83-8cef-4a31-b4c1-3f9ae596d2b2-000000@amazonses.com) Received: from a8-52.smtp-out.amazonses.com (a8-52.smtp-out.amazonses.com [54.240.8.52]) (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 4Q1wRW207jz3CBv for ; Wed, 19 Apr 2023 22:28:23 +0000 (UTC) (envelope-from 010001879ba20fc8-f6f0ee83-8cef-4a31-b4c1-3f9ae596d2b2-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=Oqoudi3336CKaZSXdVn4rgCFyX/og6MhjUFm5AtbnPg3352DJ0kt4xIWcMDmv0Kq qItpitn3DCtChtTLYIeNpZk/YWRw+pKCKHRo2tiFoKUHCCfgBnGd8h1NhcbLyTX9UMk WvxBlLCx1jRCxM6UgI5XNFluQgNIYGg+FOu9mvaM= 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=UqzOg24Z1MbMS7YVfnhASj5hxkrtqIyYWLJkLFNCTfwg9KTzgT+pVikhHKOATmoU ICRHXMZ2EzTfkpTBTZZevbXMZDBp/aICke6NOS8/KG/DEyO7rhBd4f6A1Lsuwth3ZUo kVAOWEHzqraatsmlxfdAr9xOoKOAIM+BHCl3zZKc= Message-ID: <010001879ba20fc8-f6f0ee83-8cef-4a31-b4c1-3f9ae596d2b2-000000@email.amazonses.com> Date: Wed, 19 Apr 2023 22:28:22 +0000 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.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.52 X-Rspamd-Queue-Id: 4Q1wRW207jz3CBv 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