[
https://issues.apache.org/jira/browse/ARROW-10899?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17341925#comment-17341925
]
Kirill Lykov edited comment on ARROW-10899 at 5/10/21, 2:08 PM:
----------------------------------------------------------------
I believe that the LSD implementation by Travis is stable by construction, I
will recheck it.
Regarding stable_sort – i'm trying to find a way to rely on stable_sort
instead of radix sort for particular types of distribution.
These checks are done in boost::spread_sort but I haven't got the math behind
yet.
In particular, they detect is sequence is sorted and find min/max values.
>From that they can conclude if the sequence is bucket sorted or it is not
>sorted but better to be handled by another algorithm.
was (Author: klykov):
I believe that the LSD implementation by Travis is stable by construction, I
will recheck it.
Regarding stable_sort – i'm trying to find a way to rely on stable_sort instead
of radix sort for particular types of distributions.
These checks are done in boost::spread_sort but I haven't got the math behind
yet.
> [C++] Investigate radix sort for integer arrays
> -----------------------------------------------
>
> Key: ARROW-10899
> URL: https://issues.apache.org/jira/browse/ARROW-10899
> Project: Apache Arrow
> Issue Type: Wish
> Components: C++
> Reporter: Antoine Pitrou
> Assignee: Kirill Lykov
> Priority: Major
> Attachments: Screen Shot 2021-02-09 at 17.48.13.png, Screen Shot
> 2021-02-10 at 10.58.23.png, all_random_wholeRange.png,
> all_random_wholeRange.png, all_random_wholeRange.png
>
>
> For integer arrays with a non-tiny range of values, we currently use a stable
> sort. It may be faster to use a radix sort instead.
--
This message was sent by Atlassian Jira
(v8.3.4#803005)
