solady

solady copied to clipboard

Some stuff I've considered:

• Radix sort.

  Not really very generalizable to large numbers. Need O(n) auxillary space for the straightforward implementation, which can cost more gas if the array is big (cuz of EVM's quadratic memory expansion costs)

• Bucket Sort

  Same pitfalls as Radix sort.

• Sorting networks / Unrolled sorts

  Large bytecode, needs access to the jump, swap, dup opcodes.

This sample code is 3rd fastest compared to le wild submissions on https://g.solidity.cc/.

• First submission uses bucket sort, which works well for small numbers, medium sized arrays, and uniformly distributed inputs. (maybe create two different kinds of sorts and let the user pick the one that best fit their case?) It uses sorting networks to sort the buckets.

• Second submission uses unrolled insertion sorts and jumps. But this comes at a cost of big bytecode size, like 5x more lol. Also, we can't do jumps now.

If you have any suggestions, comment / make a PR, or DM me on Twitter.

If we can cut the gas down by another 50%, many on-chain possibilities can be unlocked.