[ARROW-1571] [C++] Implement argsort kernels (sort indices) for integers using O(n) counting sort

• Type: New Feature
• Status: Resolved
• Priority: Major
• Resolution: Fixed
• Fix Version/s: 0.17.0
• Component/s: C++
• Labels: Analytics pull-request-available
• External issue URL: https://github.com/apache/arrow/issues/17584
• Assignee: Yibo Cai
• Reporter: Wes McKinney
• Created: 19/Sep/17 23:01
• Updated: 11/Jan/23 07:15
• Resolved: 02/Mar/20 21:59

Description

This function requires knowledge of the minimum and maximum of an array. If it is small enough, then an array of size maximum - minimum can be constructed and used to tabulate value frequencies and then compute the sort indices (this is called "grade up" or "grade down" in APL languages). There is generally a cross-over point where this function performs worse than mergesort or quicksort due to data locality issues

Issue Links

• depends upon: ARROW-1900 [C++] Add kernel functions for determining value range (maximum and minimum) of integer arrays
• relates to: ARROW-7526 [C++][Compute]: Optimize small integer sorting
• links to: GitHub Pull Request #6495