From nobody Wed Apr 19 21:17:54 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 4Q1ttK1krvz45F4f for ; Wed, 19 Apr 2023 21:18:01 +0000 (UTC) (envelope-from joerg@bec.de) Received: from relay4-d.mail.gandi.net (relay4-d.mail.gandi.net [217.70.183.196]) (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 4Q1ttG6H6Lz3DBg for ; Wed, 19 Apr 2023 21:17:58 +0000 (UTC) (envelope-from joerg@bec.de) Authentication-Results: mx1.freebsd.org; dkim=pass header.d=bec.de header.s=gm1 header.b=SYlzyyZ+; spf=pass (mx1.freebsd.org: domain of joerg@bec.de designates 217.70.183.196 as permitted sender) smtp.mailfrom=joerg@bec.de; dmarc=none Received: (Authenticated sender: joerg@bec.de) by mail.gandi.net (Postfix) with ESMTPSA id 0AC41E0002 for ; Wed, 19 Apr 2023 21:17:55 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bec.de; s=gm1; t=1681939076; 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=uvd1+Z/Ahq4zZorjRN0wIStUcU1kcBiBMf+VDzpV9J0=; b=SYlzyyZ+BBxUZVzuHY0kwtAN4g77UrBT+N8SpXTflTHGXNXf5kkmwPNMMr4D2wSo8HSUvS ZB9Om5hCP0oyiw8BwsQaixW9R+Pmol7C+GBEflDUpTNxc6Zr/Rjn30lEy56J7TDT1lasez CU+NBJIeI69+WudqGTRljxPkvvGhvrSQG9rLCG6vvxjJrmZl0QYxL/RODDW6sz/KrrJ6Py EMbq8/BG5/SkvTeZRMtH77a7YNuoKD4eYBTzHjHeZlqhIqk9M1EPOYeEot84MD94TdycSL GU5tt84Kk1BNwwT2YFJf9jiIkSGl2cr4O3bZjKlt8tj1V5PIxN0dPOM2C1szmA== Date: Wed, 19 Apr 2023 23:17:54 +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.70 / 15.00]; NEURAL_HAM_LONG(-1.00)[-1.000]; NEURAL_HAM_MEDIUM(-1.00)[-1.000]; NEURAL_HAM_SHORT(-1.00)[-1.000]; R_DKIM_ALLOW(-0.20)[bec.de:s=gm1]; R_SPF_ALLOW(-0.20)[+ip4:217.70.183.192/28]; MIME_GOOD(-0.10)[text/plain]; RCVD_IN_DNSWL_LOW(-0.10)[217.70.183.196:from]; RWL_MAILSPIKE_GOOD(-0.10)[217.70.183.196:from]; MID_RHS_MATCH_FROM(0.00)[]; FROM_EQ_ENVFROM(0.00)[]; MLMMJ_DEST(0.00)[dev-commits-src-all@freebsd.org]; ARC_NA(0.00)[]; MIME_TRACE(0.00)[0:+]; RCVD_COUNT_TWO(0.00)[2]; ASN(0.00)[asn:29169, ipnet:217.70.176.0/20, country:FR]; FREEFALL_USER(0.00)[joerg]; DKIM_TRACE(0.00)[bec.de:+]; FROM_HAS_DN(0.00)[]; TO_DN_NONE(0.00)[]; PREVIOUSLY_DELIVERED(0.00)[dev-commits-src-all@freebsd.org]; TO_MATCH_ENVRCPT_ALL(0.00)[]; RCPT_COUNT_ONE(0.00)[1]; DMARC_NA(0.00)[bec.de]; RCVD_TLS_ALL(0.00)[]; RCVD_VIA_SMTP_AUTH(0.00)[] X-Rspamd-Queue-Id: 4Q1ttG6H6Lz3DBg X-Spamd-Bar: --- X-ThisMailContainsUnwantedMimeParts: N Am Wed, Apr 19, 2023 at 09:27:14PM +0200 schrieb Hans Petter Selasky: > > > qsort() is frequently used to do all kinds of sorting, and some pointed out that qsort() can technically be any kind of sorting algorithm, but looking around it is not. > > > > Because there are variants that are guaranteed n log n? Which is better > > than your n log^2 n. > > Only so-called mergesort() algorithms can do sorting in O(N log N) time, > from what I know. 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. Joerg