Sorting in Solidity without Comparison

This article discusses the cost of sorting small sets of numbers in Solidity, the defacto smart contract language for the Ethereum blockchain.

Background

During the development and testing of Datona Labs’ Solidity Smart-Data-Access-Contract (S-DAC) templates, we wanted to sort some small sets of small numbers, for example:

function sortHands(Hand[noPlayers] memory hands) internal pure {
    for (uint player = 0; player < noPlayers; player++) {
        sort(hands[player].cards);
    }
}

Of course we want to use as little gas (few cycles) as possible because blockchain languages like Solidity are very expensive to run compared with normal systems and the gas actually costs a measurable amount of money.

A serious test. Photo by Inês Ferreira on Unsplash

Sorting Options

Sorting Algorithms

There are many possible sorting algorithms to consider, for instance see Merge_Sort or Quick_Sort, of which we have only considered the following for this article:

  Sort Name               Performance
  Quick Sort              O(n log n)
  Insertion Sort          O(n²)
  Counting Sort           O(n + setSize)
  Unique…