Date: Tue, 02 Jun 2026 03:40:46 +0000
From: bugzilla-noreply@freebsd.org
To: bugs@FreeBSD.org
Subject: [Bug 295784] mergesort{,_b} should accept element size smaller than sizeof(void *)
Message-ID: <bug-295784-227@https.bugs.freebsd.org/bugzilla/>
index | next in thread | raw e-mail
https://bugs.freebsd.org/bugzilla/show_bug.cgi?id=295784 Bug ID: 295784 Summary: mergesort{,_b} should accept element size smaller than sizeof(void *) Product: Base System Version: 16.0-CURRENT Hardware: Any OS: Any Status: New Severity: Affects Some People Priority: --- Component: misc Assignee: bugs@FreeBSD.org Reporter: minsoochoo0122@proton.me Currently mergesort{,_b} (see qsort(3)) do not accept element size smaller than sizeof(void *). This happens due an optimization trick to reduce heap allocation by embedding run-boundary pointers in list2 along with data. However, this is not an adequate optimization method for a standard library utility because it rejects arrays composed of basic types such as char and short. This restriction only applies to mergesort (i.e. qsort and heapsort don't have this restriction). Solution: separate pointers from list2. In worst case (size==4), the memory allocation will increase by 2x as we need O(n/2) for run-boundary pointers. Still, the nature of standard library is enough to justify this tradeoff. -- You are receiving this mail because: You are the assignee for the bug.home | help
Want to link to this message? Use this
URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?bug-295784-227>