Efficient Sorter: Showcasing the Winning Solutions

From March 4th - 17th, AgorApp heald the Efficient Sorter competition. The challenge was to implement an on-chain integer sorting algorithm by using competitive programming and gas golfing techniques.

The goal of the competition was to see who could optmize their solution with the least amount of gas.

The top winners were…

Top 3 solutions

1st place: LStan

Gas: 23883

pragma solidity 0.8.10;

contract EfficientSorter {
    // You can add more state variables here

    function run(uint256[] memory data) external pure returns(uint256[] memory) {
        // ADD YOUR CODE HERE
        assembly {
            if eq(calldataload(0x24), 1) {
                mstore(0x0, 32)
                mstore(0x20, 1)
                mstore(0x40, 0)
                return(0, 0x60)
            }

            if eq(calldataload(0x24), 4) {
                mstore(0x0, 32)
                mstore(0x20, 4)
                mstore(0x40, 3)
                mstore(0x60, 7)
                mstore(0x80, 9)
                mstore(0xa0, 56)
                return(0, 0xc0)
            }

            if eq(calldataload(0x24), 7) {
                mstore(0x0, 32)
                mstore(0x20, 7)
                mstore(0x40, 1)
                mstore(0x60, 2)
                mstore(0x80, 3)
                mstore(0xa0, 7)
                mstore(0xc0, 11)
                mstore(0xe0, 18)
                mstore(0x100, 21)
                return(0, 0x120)
            }

            mstore(0x0, 32)
            mstore(0x20, 5)

            let d0 := calldataload(0x44)
            let d1 := calldataload(0x64)
            let d2 := calldataload(0x84)
            let d3 := calldataload(0xa4)
            let d4 := calldataload(0xc4)

            if gt(d0, d1) {
                let tmp := d0
                d0 := d1
                d1 := tmp
            }

            if gt(d1, d2) {
                let tmp := d1
                d1 := d2
                d2 := tmp
            }

            if gt(d2, d3) {
                let tmp := d2
                d2 := d3
                d3 := tmp
            }

            if gt(d3, d4) {
                let tmp := d3
                d3 := d4
                d4 := tmp
            }

            if gt(d0, d1) {
                let tmp := d0
                d0 := d1
                d1 := tmp
            }

            if gt(d1, d2) {
                let tmp := d1
                d1 := d2
                d2 := tmp
            }

            if gt(d2, d3) {
                let tmp := d2
                d2 := d3
                d3 := tmp
            }

            if gt(d0, d1) {
                let tmp := d0
                d0 := d1
                d1 := tmp
            }

            if gt(d1, d2) {
                let tmp := d1
                d1 := d2
                d2 := tmp
            }

            if gt(d0, d1) {
                let tmp := d0
                d0 := d1
                d1 := tmp
            }

            mstore(0x40, d0)
            mstore(0x60, d1)
            mstore(0x80, d2)
            mstore(0xa0, d3)
            mstore(0xc0, d4)
            return(0, 0xe0)
        }
    }

    // You can add more functions here
}

2nd place: mail

Gas: 25447

pragma solidity 0.8.10;

contract EfficientSorter {
    // You can add more state variables here

    function run(uint256[] memory data) external pure returns(uint256[] memory) {
        uint256 n = data.length;
        unchecked {
            for (uint256 i = 1; i < n; i++) {
                uint256 key = data[i];
                int256 j = int256(i) - 1;
                while (j >= 0 && data[uint256(j)] > key) {
                    data[uint256(j + 1)] = data[uint256(j)];
                    j = j - 1;
                }
                data[uint256(j + 1)] = key;
            }
        }
        return data;
    }

    // You can add more functions here
}

3rd Place: cazacuchristian

Gas: 26740

pragma solidity 0.8.10;

contract EfficientSorter {
    function run(uint256[] memory data) external pure returns(uint256[] memory) {
        uint n = data.length - 1;
        for (uint i = 0; i < n; ++i) {
            uint minIndex = i;
            for (uint j = i + 1; j <= n; ++j) {
                if (data[j] < data[minIndex]) {
                    minIndex = j;
                }
            }

            if (minIndex != i) {
                (data[i], data[minIndex]) = (data[minIndex], data[i]);
            }
        }
        return data;
    }
}

Thanks for all who participated in the challenge!

Want to learn more? Follow our progress!

For the latest news and developments, including course & challenge launches, stay tuned. Join the AgorApp Discord and communicate with the team or follow us on Telegram, Twitter or Linkedin.