You are viewing a plain text version of this content. The canonical link for it is here.
Posted to user@arrow.apache.org by Martin Janda <ja...@crcdata.cz> on 2020/04/12 08:01:16 UTC
Java: Sorting with QuickSort algorithm?
I found, that Arrow [Java] sorting uses QuickSort algorithm for vectors
> 15 items. QuickSort is unstable. It means that it doesn't provide
expected results. I think that stable sort algorithm is better. It keeps
order of indices for IndexSorter and preserves order for StructVectors.
Stable sort algorithm produces same result when 1x sorted with
CombinedComparators and 2x sorted with split comparators.
Martin
Re: Java: Sorting with QuickSort algorithm?
Posted by Micah Kornfield <em...@gmail.com>.
Hi Martin,
Sorry for the late reply. For stable sort there is StableVectorComparator
[1] that works with quicksort which should provide a stable sort when used
with QuickSort (are you seeing a bug in that?). Are you suggesting
implementing a different stable sort algorithm?
Thanks,
Micah
https://github.com/apache/arrow/blob/f7fb49cfa19fe2d39dd54a426b1288d33342faf5/java/algorithm/src/main/java/org/apache/arrow/algorithm/sort/StableVectorComparator.java
On Sun, Apr 12, 2020 at 1:01 AM Martin Janda <ja...@crcdata.cz> wrote:
> I found, that Arrow [Java] sorting uses QuickSort algorithm for vectors
> > 15 items. QuickSort is unstable. It means that it doesn't provide
> expected results. I think that stable sort algorithm is better. It keeps
> order of indices for IndexSorter and preserves order for StructVectors.
>
> Stable sort algorithm produces same result when 1x sorted with
> CombinedComparators and 2x sorted with split comparators.
>
> Martin
>
>