openzeppelin-contracts

openzeppelin-contracts copied to clipboard

🧐 Motivation On-chain sorting is a risky design choice, but for small data sizes it could be useful for some algorithms. I'm proposing sorting of memory arrays, NOT storage arrays, that would be prohibitively expensive.

📝 Details This issue is basically a temperature check. The implementation of an in-memory binary heap already exists here, it's polished, optimized, benchmarked and tested. It only needs to be simplified and generalized for sorting uint256s instead of being a single-use heap for specialized user-defined types. If this issue gets a positive reception, I can do that work.

I think you're right that in-memory sorting for small bounded arrays could be acceptable and useful.

Do you have use cases in mind?

What sorting algorithm would you suggest? A binary heap isn't exactly sorting.

It would be nice to sort in place to avoid memory expansion costs.

I don't have a particular use case in mind, I just thought that it may be useful for somebody as OZ is the unofficial Solidity std-lib :shrug:

Binary heap is one loop away from being an in-place heapsort implementation, just keep popping values and append them at the end of the array where the heap lives. That's part of the work that needs to be done before submitting a complete PR.

We can do an in place quick sort like this. One usecase we recently discovered is sorting leaves when doing a multi merkle proof verify

That's a neat quicksort implementation! I can't wait to benchmark it against heapsort. Before I've implemented heapsort I was experimenting with quicksort too and the gas usage was much worse. My implementation could've been poor though :sweat_smile: