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

[Java] Implement quick sort in a non-recursive way to avoid stack overflow

    XMLWordPrintableJSON

    Details

    • Type: Improvement
    • Status: Resolved
    • Priority: Critical
    • Resolution: Fixed
    • Affects Version/s: None
    • Fix Version/s: 0.16.0
    • Component/s: Java

      Description

      The current quick sort algorithm in implemented by a recursive algorithm. The problem is that for the worst case, the number of recursive layers is equal to the length of the vector. For large vectors, this will cause stack overflow.

      To solve this problem, we implement the quick sort algorithm as a non-recursive algorithm.

        Attachments

          Issue Links

            Activity

              People

              • Assignee:
                fan_li_ya Liya Fan
                Reporter:
                fan_li_ya Liya Fan
              • Votes:
                0 Vote for this issue
                Watchers:
                2 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 - 2h 40m
                  2h 40m