[ARROW-7400] [Java] Avoids the worst case for quick sort

• Type: Improvement
• Status: Resolved
• Priority: Major
• Resolution: Fixed
• Fix Version/s: 0.17.0
• Component/s: Java
• Labels: pull-request-available
• External issue URL: https://github.com/apache/arrow/issues/23675
• Assignee: Liya Fan
• Reporter: Liya Fan
• Created: 16/Dec/19 12:08
• Updated: 11/Jan/23 07:53
• Resolved: 18/Feb/20 04:34

Description

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.

Issue Links

• links to: GitHub Pull Request #6039