[Bug 287089] [libc] qsort insertion sorts all pre-partitioned arrays, allowing trivial n^2 inputs

https://bugs.freebsd.org/bugzilla/show_bug.cgi?id=287089

Alexey Sukhoguzov <sap@eseipi.net> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |sap@eseipi.net

--- Comment #2 from Alexey Sukhoguzov <sap@eseipi.net> ---
Created attachment 262371
  --> https://bugs.freebsd.org/bugzilla/attachment.cgi?id=262371&action=edit
Disable the "switch to insertion sort" optimization (from NetBSD)

IIUC, this issue is also described thoroughly at
https://www.raygard.net/2022/02/26/Re-engineering-a-qsort-part-3.

As was mentioned in the article, both NetBSD and OpenBSD got rid of this
optimization in 2009 and 2014 respectively:

https://cvsweb.netbsd.org/bsdweb.cgi/src/lib/libc/stdlib/qsort.c#rev1.20
https://cvsweb.openbsd.org/src/lib/libc/stdlib/qsort.c#rev1.12

I didn't test those changes myself, but looks like nothing stops FreeBSD to do
exactly the same.

-- 
You are receiving this mail because:
You are the assignee for the bug.