How can I maintain a sorted list in my smart contract?

Question

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?

Answer 1

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.

Disclosure: I am the author