4

Is it crazy to feel the need to sort solidity arrays?

Imagine implementing a market (double action) you need to sort the orders. I could imagine other usecases where sort is useful. But as we all know even a for loop is dangerous in terms of gas exhaustion. What are best practices in this regard?

The search "Solidity Quicksort" returns nearly no results.

I came up with the idea of letting someone sort and upload the data back to the smart contract, then smart contract can just check if the data is right + sorted, which should be much easier than sorting. O(nlogn) versus O(n). The problem here is that the transaction size grows by O(n) now, which, I feel, could be problematic.

Any guidelines, experiences?

0

The library below provides the ability for your smart contracts to store a sorted list of uint256s.

From BokkyPooBah's Red-Black Binary Search Tree Library:

A gas-efficient Solidity library using the iterative (rather than recursive) Red-Black binary search tree algorithm to help you maintain a sorted uint key index for your data. Insertions, deletions and searches are in O(log n) time (and ~gas). Note that the key of 0 is prohibited. Use the sorted keys as indices to your mapping tables of data to access your data in sorted order.

Inserting a key into an empty tree costs 68,459 gas. Inserting a key into a tree with 9,999 keys costs 127,210 gas on average. Removing an element from a tree with a single key costs 44,835 gas. Removing a key from a tree with 10,000 keys cost 81,486 gas on average.

An important use-case for this library is to maintain a sorted on-chain order book in decentralised exchange smart contracts, providing a provably fair order matching algorithm.

The library can be found at BokkyPooBahsRedBlackTreeLibrary.sol, and an example of the usage can be found at TestBokkyPooBahsRedBlackTree.sol.

Following is a chart of the minimum, average and maximum gas cost to insert and remove items randomly (best case) and sequentially into a tree with up to 10,000 items. The x scale is log2.

Chart

Disclosure: I am the author

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.