<table border="1" cellspacing="0" cellpadding="8">
    <tr>
        <th>Issue</th>
        <td>
            <a href=https://github.com/llvm/llvm-project/issues/111495>111495</a>
        </td>
    </tr>

    <tr>
        <th>Summary</th>
        <td>
            Further improvements to quicksort implementation of qsort
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            new issue
      </td>
    </tr>

    <tr>
      <th>Assignees</th>
      <td>
      </td>
    </tr>

    <tr>
      <th>Reporter</th>
      <td>
          statham-arm
      </td>
    </tr>
</table>

<pre>
    llvm-libc's `qsort`, the Quicksort version, works but is not especially polished.

In a recent PR (#110849) @michaelrj-google [observed](https://github.com/llvm/llvm-project/pull/110849#pullrequestreview-2352848252) that more of the functions in the quicksort headers should be marked with `LIBC_INLINE`, so that the top-level `qsort` function doesn't incur any internal function-call overheads _except_ when actually recursing.

It might also be worth considering other standard optimizations commonly used in quicksort algorithms (after benchmarking to make sure they really are improvements):
* make sure we have the best choice of partitioning strategy. Currently we always pick the element in the middle, which at least behaves reasonably if the input list is already mostly sorted (better than picking the start or end element). But median of (start, middle, end) is a common choice; maybe that's better?
* consider not recursing right down to lists of size 2, but instead, stop when every remaining sublist has size at most 8 or 16 or something like that, and then finish up with a pass of insertion sort
* adopt "introsort", a variation of quicksort in which you detect when your sublists aren't getting smaller fast enough, and switch over to heapsort. That way you still keep most of quicksort's good constant factor, but remove the quadratic-time worst case, because that's the case where heapsort takes over.
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJyUVU1v4zgP_jXKhUjgKE6THHKYtm-BAoPBu4u9D2iJsTSRJVekk838-oXkpu0e9-Iglik-fD4kZPZ9JDqq7aPaPi9wEpfykQXF4bDEPCy6ZG_HEC7DMvjOKL1jUA_NG6cs6qFR-gnEEfwxeXMu7-BCmX2KZeGa8pmhmwQ8Q0wCxCMZjyHcYEzBsyO7Us2zar7Nz9cICJkMRYH__wlK75XerNfNvj0ofQDVNoM3DinkX8s-pT4QqO1j6pjyhazaPiu9dyIjq803pV-Ufum9uKlbmTQo_VKmeP9Zjjn9IiNKv4xTCEq_3Ntsyv9MbxOxZLp4ui71Zqv37V5vdUEhDgWGlAnSqc5-mqIRnyKDj_XF2wcZjtBSZmCXpmChIxgwn8nC1YsrPH5_fXz6-frj--uP_72zyWnuUDaSNC4DXSh8pfyjH9hEHJXeCfhopgwYb-CjUI4YPr5aGgwB0oVyAcPwk_42NMpPuDqKgEamqkcmM2X2sf-3IAKD750ABk4F_jVlcWBSZG8p-9hDEkcZWDBazBbSKH7wv3EmxKRhSDHcYGKyhZ5PajD0KXtxAxed8SSUoaNoXGGobCwJBjwT8JSpsFEwVqiYCfww5nShgaKw0oei9wxbf_tSdSVweKnV0BELGJe8qcKNmMUXkKUVS0ah_raCpylnihJupRbDFW8MozfnugWF2vAu8-CtDVSN7rxxgAKBkAU6Kl254OUUsQs38LNVfBwngeC5RgJDJrQ3GBKXjoUWsoWNjqTQIQ5j7V7pcFRYzgIpA0V7R6P0YQWPk8BA1mMssym9r18WaJ8gKdpi39L3XZd3OtTmEQa8dVSNVxM-A1Cbl09W75rXIH-4BXK1h03XWAQrk3GBwP43gS5ta_wjC6Gt9pY0ztajC-Wi6YB-FmHqKjEOeS6vMWOBfZl4_VCenAYSV74O_nzH-wQYbeEnwslHzw6mcQ4Ywohc8fjIlGtoaoo-pkKbRgGltY-SU13TFTbCBbOvNi71n7718V3uW5rAkpCReZ5bmvJ9CC4mnaPZk0gdb8AQKMOpOIRimnp3h85XL8bVjBYSHeFYWq3gr3IQXPFWe7H4EOBMNM60fEVVRetTslUmwShwQiMp3xXINKT3ILxNaDOKN0vxQ010CQZyNUlHBif-4oRSURbLjJk-sIHgmbhCXi3scWMPmwMu6Lje6f1m1-rmsHBHuyVq2lOLD8YQmgO2zWmz17tm97Bt9l278Efd6HbdNPtmt31oD6v1HrVud7vGamxoTaptij_CqpzZq5T7hWee6Lher9vDdhGwo8D18tI60hXqalFw-7zI863VTT2rtqmqfG4jXgIdX6ZcT6-vp0lR4IvawzjH7NMJ5f1iyuH4n2-aio7rXVPhX476nwAAAP__3kGZYw">