[Bug 295784] mergesort{,_b} should accept element size smaller than sizeof(void *)

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.