arrow

ARROW-6306: [Java] Support stable sort by stable comparators

Stable sort is desirable in many scenarios. It means equal elements preserve their relative order after sorting.

There are stable sort algorithms. However, in practice, the best sort algorithm is quick sort and quick sort is not stable.

To make the best of both worlds, we support stable sort by stable comparators. It differs from an ordinary comparator in that it breaks ties by comparing the value indices.

With the stable comparator, the quick sort algorithm becomes a stable algorithm.

Closes #5153 from liyafan82/fly_0821_stable and squashes the following commits:

047e3b107 <liyafan82>  Support stable sort by stable comparators

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