[petsc-dev] PETSc Sorting with duplicate entries

[Todd Munson]

> 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().

Why can't the sort routine simply use two comparisons?  In particular,
you use the value as the first comparison and in case of ties use the 
index to break ties?  This means that there are no identical values 
assuming all indices are unique.

Cheers, Todd.