[petsc-dev] PETSc Sorting with duplicate entries

[Hong Zhang]

Gautam:

> I'm was sorting an array which that has duplicate entries: (x = [39 9 19 39 29]). I noticed that for duplicate entries after sorting, the index returned are not in ascending. The example below will explain this further.
>
> Here is the code snippet:
>
> ============================================
> do ii=1,5
> index(ii) = ii
> endo
>
> index = index -1
> call PetscSortIntWithPermutation( 5, x, index, ierr)
> index = index + 1
>
> do ii=1,5
> write(*,*), x(ii), index(ii), x(index(ii))
> enddo
> ============================================
>
>
> Output:
>          39           2           9
>            9           3          19
>          19           5          29
>          39           4          39
>          29           1          39
>
PetscSortIntWithPermutation() implements bubble sort for n<8 and
insertion sort otherwise,
which does not give ordered index for duplicate entries. If you can
find the algorithm used by Matlab, please
let us know. We can implement it. Otherwise, I think you may write a
subroutine to sort index() of
duplicate entries, which takes O(n) operations, a low order operation
comparing to sort().

Hong

> Output (Expected by me, similar to MATLAB output): Note the difference in the index(4) and index(5) values
>          39           2           9
>            9           3          19
>          19           5          29
>          39           1          39
>          29           4          39
>
>
> I tired using PetscSortIntWithArray and go similar result. I was wondering if there is a sorting option that can get me the output which I'm expecting. The only way around I came up for this was to look at the index(:) entries that correspond to duplicate values and sort them again.
>
>
> -Gautam.
>