3 ms·

Well, I know what you mean but "completely different" is potentially misleading here. The current ipnsort is using bidirectional merges developed for quadsort (

Well, I know what you mean but "completely different" is potentially misleading here. The current ipnsort is using bidirectional merges developed for quadsort (the merging part of fluxsort) and the fulcrum partition from crumsort, also by Scandum (all credited in comments; check the source if you want to see more influences!). To balance things out, the strategy for using the namesake sorting networks is new to me: pick a few fixed sizes and handle the rest by rounding down then a few steps of insertion sorting.

Voultapher 3y ago
I should clarify, I meant that ipn_stable and ipn_unstable were separate projects, albeit with some cross-over ideas. I can't rule out that someone else had that idea for limiting the use of sorting-networks, all I can say is that I came up with that myself. At the same time a lot of the good ideas in ipnsort are ideas from other people, and I try my best to accredit them. As I commented before, my goal is not peak perf for integers at any cost. Here is a commit https://github.com/Voultapher/sort-research-rs/commit/d908feb0070717510ddc20b632c1568ce6949b0a https://github.com/Voultapher/sort-research-rs/commit/d908fe... that improves perf by 7% across sizes for the random pattern. But that comes with a non negligible binary size and compile time impact even for integers. And while I use heuristics to only use sorting-networks where sensible, they can guess wrong. This is a generic sort implementation with the goal of being a good all-round implementation fit for a standard library and those various uses.
scandum 3y ago
"pick a few fixed sizes and handle the rest by rounding down then a few steps of insertion sorting." I'm late to the party, but this sounds a lot like quadsort's small array handling: Sort 4, 8, or 16 elements using unrolled parity merges, and handle the rest with insertion sorting. An unrolled parity merge can be viewed as a stable sorting network. I never added unstable sorting networks to crumsort due to wanting to keep the code size low, and perhaps the mistaken idea that it would reduce adaptivity, as crumsort is likely to scramble partially sorted input.

Voultapher 3y ago

I should clarify, I meant that ipn_stable and ipn_unstable were separate projects, albeit with some cross-over ideas. I can't rule out that someone else had that idea for limiting the use of sorting-networks, all I can say is that I came up with that myself. At the same time a lot of the good ideas in ipnsort are ideas from other people, and I try my best to accredit them. As I commented before, my goal is not peak perf for integers at any cost. Here is a commit https://github.com/Voultapher/sort-research-rs/commit/d908feb0070717510ddc20b632c1568ce6949b0a https://github.com/Voultapher/sort-research-rs/commit/d908fe... that improves perf by 7% across sizes for the random pattern. But that comes with a non negligible binary size and compile time impact even for integers. And while I use heuristics to only use sorting-networks where sensible, they can guess wrong. This is a generic sort implementation with the goal of being a good all-round implementation fit for a standard library and those various uses.

scandum 3y ago

"pick a few fixed sizes and handle the rest by rounding down then a few steps of insertion sorting." I'm late to the party, but this sounds a lot like quadsort's small array handling: Sort 4, 8, or 16 elements using unrolled parity merges, and handle the rest with insertion sorting. An unrolled parity merge can be viewed as a stable sorting network. I never added unstable sorting networks to crumsort due to wanting to keep the code size low, and perhaps the mistaken idea that it would reduce adaptivity, as crumsort is likely to scramble partially sorted input.