arrow-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Micah Kornfield <emkornfi...@gmail.com>
Subject Re: Java: Sorting with QuickSort algorithm?
Date Sun, 26 Apr 2020 23:46:02 GMT
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 <jandam@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
>
>

Mime
View raw message