[petsc-dev] PETSc Sorting with duplicate entries

[Barry Smith]

On Mar 31, 2011, at 11:34 AM, Todd Munson wrote:

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

  This results in a slower sort than one that ignores the index values. Usually one wants sorts to be as fast as possible so we don't include this. If you want the double sort you should provide that as "yet another routine" that would be called by people who care about this additional feature.

   Barry

> 
> Cheers, Todd.
>