SimultaneousSortperm

The SimultaneousSortperm package provides functions that mimic sortperm and sortperm!, but achieve better performance for large input sizes by simultaneously sorting the data and index vector. First the data is sorted using the unstable Pattern-Defeating-Quicksort algorithm while simultaneously moving the corresponding indices. In a second pass, all subarrays with equal data elements are sorted according to their indices to ensure stability.

The following functions are exported:

• ssortperm(v) – Return a permutation vector p that puts v[p] in sorted order.
• ssortperm!(ix, v) – Modify vector ix so that v[ix] is in sorted order.
• ssortperm!(v) – Sort v and return the permutation vector p that was used to put v in sorted order.
• ssortperm!!(ix, v) – Sort v and modify the vector ix, so that it contains the permutation which was used to put v in sorted order.

Benchmarks

More benchmark results can be found here.

Roadmap

• Use pattern-defeating-quicksort from SortingAlgorithms when PR is merged.
• Contribute to Base / SortingAlgorithms

Possible Improvements / Changes

• Improve optimization for very small inputs.
• Use allocating optimizations when dims keyword is used?
• Include option to use different sorting algorithms?