linux-kernel - [PATCH 2/4] lib/sort: Fix outdated comment regarding glibc qsort()

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date: Tue, 28 May 2024 04:30:09 +0800
From: Kuan-Wei Chiu <visitorckw@...il.com>
To: akpm@...ux-foundation.org
Cc: jserv@...s.ncku.edu.tw,
	linux-kernel@...r.kernel.org,
	Kuan-Wei Chiu <visitorckw@...il.com>
Subject: [PATCH 2/4] lib/sort: Fix outdated comment regarding glibc qsort()

The existing comment in lib/sort refers to glibc qsort() using
quicksort. However, glibc qsort() no longer uses quicksort; it now uses
mergesort and falls back to heapsort if memory allocation for mergesort
fails. This makes the comment outdated and incorrect.

Update the comment to refer to quicksort in general rather than glibc's
implementation to provide accurate information about the comparisons
and trade-offs without implying an outdated implementation.

Signed-off-by: Kuan-Wei Chiu <visitorckw@...il.com>
---
 lib/sort.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/lib/sort.c b/lib/sort.c
index 651b73205f6d..b918ae15302d 100644
--- a/lib/sort.c
+++ b/lib/sort.c
@@ -5,7 +5,7 @@
  * This performs n*log2(n) + 0.37*n + o(n) comparisons on average,
  * and 1.5*n*log2(n) + O(n) in the (very contrived) worst case.
  *
- * Glibc qsort() manages n*log2(n) - 1.26*n for random inputs (1.63*n
+ * Quicksort manages n*log2(n) - 1.26*n for random inputs (1.63*n
  * better) at the expense of stack usage and much larger code to avoid
  * quicksort's O(n^2) worst case.
  */
-- 
2.34.1