Liya Fan created ARROW-7400:
-------------------------------
Summary: [Java] Avoids the worst case for quick sort
Key: ARROW-7400
URL: https://issues.apache.org/jira/browse/ARROW-7400
Project: Apache Arrow
Issue Type: Improvement
Components: Java
Reporter: Liya Fan
Assignee: Liya Fan
This issue is in response of a discussion in:
https://github.com/apache/arrow/pull/5540#discussion_r329487232.
The quick sort algorithm can degenerate to an O(n^2) algorithm, if the pivot is
selected poorly. This is an important problem, as the worst case can happen, if
the input vector is alrady sorted, which is frequently encountered in practice.
After some investigation, we solve the problem with a simple but effective
approach: take 3 samples and choose the median (with at most 3 comparisons) as
the pivot. This sorts the vector which is already sorted in O(nlogn) time.
--
This message was sent by Atlassian Jira
(v8.3.4#803005)
