From nobody Thu Apr 20 09:20:05 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 4Q2Bvd0p8Vz46Yyj for ; Thu, 20 Apr 2023 09:20:13 +0000 (UTC) (envelope-from joerg@bec.de) Received: from relay10.mail.gandi.net (relay10.mail.gandi.net [IPv6:2001:4b98:dc4:8::230]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (Client did not present a certificate) by mx1.freebsd.org (Postfix) with ESMTPS id 4Q2Bvb2D1Xz4Kl4 for ; Thu, 20 Apr 2023 09:20:11 +0000 (UTC) (envelope-from joerg@bec.de) Authentication-Results: mx1.freebsd.org; dkim=pass header.d=bec.de header.s=gm1 header.b=VTxFEeP3; spf=pass (mx1.freebsd.org: domain of joerg@bec.de designates 2001:4b98:dc4:8::230 as permitted sender) smtp.mailfrom=joerg@bec.de; dmarc=none Received: (Authenticated sender: joerg@bec.de) by mail.gandi.net (Postfix) with ESMTPSA id ACFB6240007 for ; Thu, 20 Apr 2023 09:20:07 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bec.de; s=gm1; t=1681982407; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: in-reply-to:in-reply-to:references:references; bh=IUzX4yhH9zTD9LoTsrHX9rGeT16BMHupU8zbI7mg1FU=; b=VTxFEeP3l85wHmh6Eisywlg9ZcPBieHJp4g1q5ZETTGtXDVWGGfICXgpi6rnqRhymzOYQF Yn4zPvAxkrHs320tmd2rGvt05AzzTMggUoN5FGDnPtiBOmPsKp67PdsoAXnjBAGRQ1QXas fkcqz09J0hKrExRN8sU+3NKMAqSIwFPaaM9YPs/h2mTWIkMvTM7oOyhxhu4wbzvosqZ85V 4JQOOpMt/SSz6wvN9CkKsnq+msZpJx3arUXGGSstrDLXzfzEoZ37WERX3AOZHr3CGqxp/+ My4rUDkg4Nge8gZmnwekasrq0DVV3FsKW4hiGAUSv2KAN8nwT0cFvvKEMKi1Lg== Date: Thu, 20 Apr 2023 11:20:05 +0200 From: Joerg Sonnenberger To: dev-commits-src-all@freebsd.org Subject: Re: git: 8dcf3a82c54c - main - libc: Implement bsort(3) a bitonic type of sorting algorithm.] Message-ID: References: <202304191206.33JC6Qcp062380@gitrepo.freebsd.org> <3B5734C4-8630-4CD5-BA8D-DE33899161F1@freebsd.org> 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 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: X-Spamd-Result: default: False [-3.60 / 15.00]; NEURAL_HAM_LONG(-1.00)[-1.000]; NEURAL_HAM_MEDIUM(-1.00)[-1.000]; NEURAL_HAM_SHORT(-1.00)[-1.000]; R_SPF_ALLOW(-0.20)[+ip6:2001:4b98:dc4:8::/64]; R_DKIM_ALLOW(-0.20)[bec.de:s=gm1]; MIME_GOOD(-0.10)[text/plain]; RCVD_IN_DNSWL_LOW(-0.10)[2001:4b98:dc4:8::230:from]; FROM_EQ_ENVFROM(0.00)[]; RCVD_COUNT_TWO(0.00)[2]; DKIM_TRACE(0.00)[bec.de:+]; BLOCKLISTDE_FAIL(0.00)[2001:4b98:dc4:8::230:server fail]; MIME_TRACE(0.00)[0:+]; ASN(0.00)[asn:29169, ipnet:2001:4b98::/32, country:FR]; MLMMJ_DEST(0.00)[dev-commits-src-all@freebsd.org]; DMARC_NA(0.00)[bec.de]; RCPT_COUNT_ONE(0.00)[1]; FROM_HAS_DN(0.00)[]; FREEFALL_USER(0.00)[joerg]; ARC_NA(0.00)[]; RCVD_TLS_ALL(0.00)[]; TO_MATCH_ENVRCPT_ALL(0.00)[]; PREVIOUSLY_DELIVERED(0.00)[dev-commits-src-all@freebsd.org]; MID_RHS_MATCH_FROM(0.00)[]; TO_DN_NONE(0.00)[]; RCVD_VIA_SMTP_AUTH(0.00)[] X-Rspamd-Queue-Id: 4Q2Bvb2D1Xz4Kl4 X-Spamd-Bar: --- X-ThisMailContainsUnwantedMimeParts: N 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. Joerg