From nobody Thu Apr 20 11:23:18 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 4Q2Fdj60gkz46gQf for ; Thu, 20 Apr 2023 11:23:21 +0000 (UTC) (envelope-from hps@selasky.org) Received: from mail.turbocat.net (turbocat.net [88.99.82.50]) (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 4Q2Fdj1VkBz4LXk for ; Thu, 20 Apr 2023 11:23:21 +0000 (UTC) (envelope-from hps@selasky.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) server-digest SHA256) (No client certificate requested) by mail.turbocat.net (Postfix) with ESMTPSA id 3FC982601C7; Thu, 20 Apr 2023 13:23:19 +0200 (CEST) Message-ID: Date: Thu, 20 Apr 2023 13:23:18 +0200 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.10.0 Subject: Re: git: 8dcf3a82c54c - main - libc: Implement bsort(3) a bitonic type of sorting algorithm.] To: Joerg Sonnenberger , dev-commits-src-all@freebsd.org References: <202304191206.33JC6Qcp062380@gitrepo.freebsd.org> <3B5734C4-8630-4CD5-BA8D-DE33899161F1@freebsd.org> Content-Language: en-US From: Hans Petter Selasky In-Reply-To: Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit X-Rspamd-Queue-Id: 4Q2Fdj1VkBz4LXk X-Spamd-Bar: ---- X-Spamd-Result: default: False [-4.00 / 15.00]; REPLY(-4.00)[]; ASN(0.00)[asn:24940, ipnet:88.99.0.0/16, 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 11:20, Joerg Sonnenberger wrote: > Am Wed, Apr 19, 2023 at 11:47:35PM +0200 schrieb Hans Petter Selasky: >> On 4/19/23 23:17, Joerg Sonnenberger wrote: >>> That's false. The difficult part of QuickSort is the median selection. >>> This can be done in O(n) using the median of median algorithm and when >>> combined into the main algorithm, much of the work for the median >>> selection also helps the partition step. >> >> Hi Joerg, >> >> From what I know, they all fall back to other sorting algorithms using >> malloc(), in the end. > > Please, just go and read: > Blum, Floy, Pratt, Rivest, Tarjan: Time Bounds for Selection, 1973. > [https://people.csail.mit.edu/rivest/pubs/BFPRT73.pdf] > > If you want a slightly more variant: > Alexandrescu: Fast Deterministic Selection, 2017. > [http://erdani.org/research/sea2017.pdf] > > Short answer: QuickSort requires O(log N) extra space, which is > essentially a fixed cost given the natural address space limitations. > Unless operating in a seriously confined environment, that's a perfectly > fine use of the regular stack. Hi Joerg, Thanks for the references you've provided. After reading through the paper from 1973, I have the impressions it is about solving the so-called pivot selection problem. The basic QuickSort idea was introduced in 1961, according to the paper you referred to: C. A. R. HOaRE, Find (Algorithm 65), Communications of the ACM, July 1961, pp. 321-32 The other paper you refer to: http://erdani.org/research/sea2017.pdf is about different ways to implement QuickSort and how to mitigate problems about pivot selection and performance. Looking around, qsort() in libc's around the globe is so-to-speak equivalent to variants of QuickSort: Example 1: Android https://android.googlesource.com/platform/bionic/+/754c178ae551aedcbbfd3bfd1c1c3b710d9ad989/libc/stdlib/qsort.c Example 2: Linux (GLibc) https://github.com/lattera/glibc/blob/master/stdlib/qsort.c Example 3: NetBSD http://cvsweb.netbsd.org/bsdweb.cgi/src/lib/libc/stdlib/qsort.c?rev=1.23&content-type=text/x-cvsweb-markup Example 4: Darwin https://github.com/apple/darwin-xnu/blob/main/bsd/kern/qsort.c And FreeBSD of course. Why not allow for more sorting competition inside FreeBSD? If libc is not the place, maybe an own library, like libsort is more appropriate? Would that be any better if bsort(3) was in its own library, and developed from that? --HPS