Actually I spoke too quickly, we now have:

IndexError: Out of bounds on buffer access (axis 0)

https://dev.azure.com/scikit-learn/scikit-learn/_build/results?buildId=42268&view=logs&j=c8afde5f-ef70-5983-62e8-c6b665ad6161&t=7fc5d80c-d67c-560e-65a2-6822419a270a

that was previously fixed in main.

We also need to document this fix in the 1.1.1 changelog similar to https://github.com/scikit-learn/scikit-learn/pull/23404/files#diff-5a8a66bfe0792b4a0e50eb7c8cc929f2a8e0d4d88ac2d0084e07b70d069ced89R39

how to consolidate the 2 introsort/quicksort implementation with more extensive benchmarking for various data distributions.

I actually looked at the std::sort that should be an introsort and available in Cython.
However, since we want to do a simultaneous sort the indices and from values, it makes it quite hard to use. Indeed, you want a comparator that needs to rely on a closure (that is in a Cython class furthermore). I could find the following information that shows the pattern: https://stackoverflow.com/a/63800579/6513708

Indeed, you want a comparator that needs to rely on a closure (that is in a Cython class furthermore). I could find the following information that shows the pattern: https://stackoverflow.com/a/63800579/6513708

Nice trick! +1 for a follow-up PR for 1.2.

To use the comparator, we would need to represent the values and indices as an "array of structures". Currently, it is an "structure of arrays".

As for this PR, I am +1 on it as well. Backporting this fix should be easier, since the version on 1.1.X still uses pointers.

To use the comparator, we would need to represent the values and indices as an "array of structures". Currently, it is an "structure of arrays".

Here we only have an array of values (feature values) and an array of indices (sample indices) to sort, isn't it?

Here we only have an array of values (feature values) and an array of indices (sample indices) to sort, isn't it?

This representation is like a "structure of arrays". Currently, the code is similar to this:

struct MyArrays:
    double* values_array
    int* indices_array

and dual_swap has the index to follow the value.

To use a comparator, the values and indices need to be it's own structure:

struct ValueIndex:
    double value
    int indices

ValueIndex* array_to_sort

This way the index will follow the value when value gets sorted. (The comparator will only consider value for sorting purposes)

@thomasjpfan the code snippet in https://stackoverflow.com/a/63800579/6513708 shows how to do it directly with a structure of arrays without materializing it as an array of index-value pairs, no? Although I am not sure how it works.

EDIT: actually this solution would not inplace-sort the values, only the indices. We would need an extra step to re-shuffle the values based on the sorted indices which would require a temporary copy. Not necessarily a big deal but we will need to keep that temp buffer around to avoid reallocating it each time. Not sure it's worth it and I am not sure about the CPU cache impact of this extra shuffle w.r.t. the existing inplace implementation.