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

• Type: Improvement
• Status: Resolved
• Priority: Critical
• Resolution: Fixed
• Fix Version/s: 0.16.0
• Component/s: Java
• Labels: pull-request-available
• External issue URL: https://github.com/apache/arrow/issues/23073
• Assignee: Liya Fan
• Reporter: Liya Fan
• Created: 29/Sep/19 12:05
• Updated: 11/Jan/23 07:49
• Resolved: 12/Oct/19 05:29

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.

Issue Links

• links to: GitHub Pull Request #5540