From nobody Wed Apr 19 21:47:35 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 4Q1vXS36nlz45GWm for ; Wed, 19 Apr 2023 21:47:36 +0000 (UTC) (envelope-from hps@selasky.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 4Q1vXS28Y4z4LnV for ; Wed, 19 Apr 2023 21:47:36 +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)) (No client certificate requested) by mail.turbocat.net (Postfix) with ESMTPSA id 25B20260220; Wed, 19 Apr 2023 23:47:35 +0200 (CEST) Message-ID: Date: Wed, 19 Apr 2023 23:47:35 +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. Content-Language: en-US To: Joerg Sonnenberger , dev-commits-src-all@freebsd.org References: <202304191206.33JC6Qcp062380@gitrepo.freebsd.org> <3B5734C4-8630-4CD5-BA8D-DE33899161F1@freebsd.org> From: Hans Petter Selasky In-Reply-To: Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit X-Rspamd-Queue-Id: 4Q1vXS28Y4z4LnV 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/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. They keep track of the sorting cost, and then at some point give up, finding a good median. So called radix sorting is more appropriate for doing split partition sorting, where you have not just +1/0/-1 as return values from the compare() callback function, but an actual N-bit indexer. This limits the complexity and recursion. Sometimes when you know the data to be sorted well, qsort() works great, but other times not. And there should be more options in FreeBSD, in my opinion. --HPS