You are viewing a plain text version of this content. The canonical link for it is here.

Posted to dev@arrow.apache.org by "Liya Fan (Jira)" <ji...@apache.org> on 2019/09/29 12:06:00 UTC

[jira] [Created] (ARROW-6732) [Java] Implement quick sort in a non-recursive way to avoid stack overflow

Liya Fan created ARROW-6732:
-------------------------------

             Summary: [Java] Implement quick sort in a non-recursive way to avoid stack overflow
                 Key: ARROW-6732
                 URL: https://issues.apache.org/jira/browse/ARROW-6732
             Project: Apache Arrow
          Issue Type: Improvement
          Components: Java
            Reporter: Liya Fan
            Assignee: Liya Fan


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.



--
This message was sent by Atlassian Jira
(v8.3.4#803005)