search

scandum / fluxsort

A fast branchless stable quicksort / mergesort hybrid that is highly adaptive.
The Unlicense
697 stars 23 forks source link

Tracking Reordering #9

Open diwot opened 2 months ago

diwot commented 2 months ago

Hi, is there a way to track the reordering during the sort process? Some other sort implementations (e. g Array.Sort(...) in the NET framework) allow to provide a key and a value array where the sorting only uses keys for order comparisons. The values can be used to pass in an indexer array with the identity map which then allows to track which element moved where during the sort. I was stumbling over fluxsort (which is a great project by the way) while looking for a faster search algorithm for a project I'm working on where I need to sort 64bit keys and there I need a map to know where each value was located before the sort was applied.

scandum commented 2 months ago

I'm not entirely sure what you mean, but maybe the quadsort_size routine in quadsort.h does something similar?

It creates an array of pointers, sorts them, and then copies the values where they belong. Useful when sorting large structures.