[ https://issues.apache.org/jira/browse/ARROW-10899?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17282023#comment-17282023 ]
Kirill Lykov commented on ARROW-10899: -------------------------------------- Your intuition is correct, at least for int32_t key. I benchmarked separately from arrow std::sort, std::stable_sort, boost::spreadsort, myNaiveRadixSort. And surprisingly to me even naive radix sort is faster than std sorts. But boost's spread sort is better. Y-axis is kMilliseconds, X-axis is number of elements in the array. !Screen Shot 2021-02-09 at 17.48.13.png! > [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 > > > 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)