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?

1 Answer 1

5

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

4
  • 1
    I would like to use this library, but I need to change it a bit (I need signed int). I can see that the license is MIT and so I suppose I can do whatever I want. I am thinking to rename the library to RedBlack but leave your comments at the header of the class. Is that okay with you? Jul 24, 2021 at 14:22
  • @privacyisahumanright.eth Thanks; I just wanted to ask if there is an updated version of this lib for solidity 0.8.0?
    – Sky
    Jan 27, 2023 at 12:26
  • Not yet. Use Etherscan's smart contract search for "rotateLeft" and you can find some recent implementations Jan 28, 2023 at 19:22
  • @privacyisahumanright.eth, thanks for the reply; however, it seems 0.6.0 version has no braking changes when compiled with 0.8.3 (I do lose some gas efficiency, but I will fix that later). I wondered if there would be a chance for me to contact you. (I will be using your lib extensively, so I will be creating a battery of tests). Therefore I wanted to contribute in that way. But I do have some additional 5min questions, so I would like to align with you.
    – Sky
    Jan 30, 2023 at 8:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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