arrow

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

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.

Closes #6039 from liyafan82/fly_1213_sort and squashes the following commits:

0943b0692 <liyafan82>  Make tests more readable
7cdf0a694 <liyafan82>  Fix the bug of choosing pivot and add more tests
e6ab2bf1f <liyafan82>  Apply insertion sort when the range is small
1167176b4 <liyafan82>  Avoids the worst case for quick sort

Authored-by: liyafan82 <fan_li_ya@foxmail.com>
Signed-off-by: Micah Kornfield <emkornfield@gmail.com>