Uploaded image for project: 'Apache Arrow'
  1. Apache Arrow
  2. ARROW-1571

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

Details

    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

      Attachments

        1. e5-2650.png
          111 kB
          Yibo Cai

        Issue Links

          Activity

            People

              yibocai Yibo Cai
              wesm Wes McKinney
              Votes:
              0 Vote for this issue
              Watchers:
              3 Start watching this issue

              Dates

                Created:
                Updated:
                Resolved:

                Time Tracking

                  Estimated:
                  Original Estimate - Not Specified
                  Not Specified
                  Remaining:
                  Remaining Estimate - 0h
                  0h
                  Logged:
                  Time Spent - 4h 40m
                  4h 40m

                  Slack

                    Issue deployment