Sort

README.md

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)

• Sorting networks.

  Comes with a tradeoff.

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

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

• Second submission uses sorting networks 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, DM me on Twitter.

Gas.txt

[PASS] testSort(uint256[]) (runs: 256, μ: 205054, ~: 134559)
[PASS] testSortAddressesPsuedorandom() (gas: 103497)
[PASS] testSortAddressesPsuedorandomBrutalizeUpperBits() (gas: 120172)
[PASS] testSortAddressesReversed() (gas: 48034)
[PASS] testSortAddressesSorted() (gas: 42836)
[PASS] testSortBasicCase() (gas: 1162)
[PASS] testSortChecksumed(uint256[]) (runs: 256, μ: 234890, ~: 187510)
[PASS] testSortDifferential(uint256[]) (runs: 256, μ: 364401, ~: 259345)
[PASS] testSortOriginalPsuedorandom() (gas: 217943)
[PASS] testSortOriginalReversed() (gas: 160186)
[PASS] testSortOriginalSorted() (gas: 146106)
[PASS] testSortPsuedorandom() (gas: 100475)
[PASS] testSortReversed() (gas: 44989)
[PASS] testSortSorted() (gas: 39771)

Sort.sol

// SPDX-License-Identifier: MIT
// Author: vectorized.eth
pragma solidity >=0.8.0;

/// @notice Gas optimized quick sort.
library Sort {
    // For efficient rounding down to a multiple of `0x20`.
    uint256 private constant LCG_MASK = 0xffffffffffffffe0;

    // From MINSTD.
    // See: https://en.wikipedia.org/wiki/Lehmer_random_number_generator#Parameters_in_common_use
    uint256 private constant LCG_MULTIPLIER = 48271;

    // For the linear congruential generator.
    uint256 private constant LCG_MODULO = 0x7fffffff;

    // This must be co-prime to `LCG_MODULO`.
    uint256 private constant LCG_SEED = 0xbeef;

    function sort(uint256[] memory a) internal pure {
        // Compared to regular Solidity quick sort, it can save more than 50% gas.
        assembly {
            let n := mload(a) // Length of `a`.
            mstore(a, 0) // For insertion sort's inner loop to terminate.

            // Let the stack be the start of the free memory.
            let stackBottom := mload(0x40)
            let stack := add(stackBottom, 0x40) 

            {
                // Push `l` and `h` to the stack.
                // The `shl` by 5 is equivalent to multiplying by `0x20`.
                let l := add(a, 0x20)
                let h := add(a, shl(5, n))
                mstore(stackBottom, l)
                mstore(add(stackBottom, 0x20), h)

                let s := 0 // Number of out of order elements.
                let u := mload(l) // Previous slot value, `u`.
                // prettier-ignore
                for { let j := add(l, 0x20) } iszero(gt(j, h)) { j := add(j, 0x20) } {
                    let v := mload(j) // Current slot value, `v`.
                    s := add(s, gt(u, v)) // Increment `s` by 1 if out of order.
                    u := v // Set previous slot value to current slot value.
                }
                // If the array is sorted, or reverse sorted,
                // subtract `0x40` from `stack` to make it equal to `stackBottom`,
                // which skips the sort. 
                // `shl` 6 is equivalent to multiplying by `0x40`.
                stack := sub(stack, shl(6, or(iszero(s), eq(add(s, 1), n))))

                // If 50% or more of the elements are out of order,
                // reverse the array.
                if iszero(lt(shl(1, s), n)) {
                    // prettier-ignore
                    for {} lt(l, h) {} {
                        let t := mload(l)
                        mstore(l, mload(h))
                        mstore(h, t)
                        h := sub(h, 0x20)
                        l := add(l, 0x20)
                    }
                }
            }

            // Linear congruential generator (LCG) for psuedo-random partitioning
            // to prevent idiosyncratic worse case behaviour.
            let lcg := LCG_SEED
            // prettier-ignore
            for {} iszero(eq(stack, stackBottom)) {} {
                // Pop `l` and `h` from the stack.
                stack := sub(stack, 0x40)
                let l := mload(stack)
                let h := mload(add(stack, 0x20))

                switch shr(9, sub(h, l))
                case 0 {
                    // Do insertion sort if `h - l < 0x20 * 16`.
                    // prettier-ignore
                    for { let i := add(l, 0x20) } iszero(gt(i, h)) { i := add(i, 0x20) } {
                        let k := mload(i) // Key.
                        let j := i // The current slot.
                        let b := sub(j, 0x20) // The slot before the current slot.
                        let v := mload(b) // The value of `b`.
                        // prettier-ignore
                        for {} gt(v, k) {} {
                            mstore(j, v)
                            j := b
                            b := sub(b, 0x20)
                            v := mload(b)
                        }
                        mstore(j, k)
                    }
                }
                default {
                    // Psuedo-random partition pivot.
                    lcg := mulmod(lcg, LCG_MULTIPLIER, LCG_MODULO) // Step the LCG.
                    let p := and(sub(h, mod(lcg, sub(h, l))), LCG_MASK) // Pivot slot.
                    let x := mload(p) // The value of the pivot slot.
                    // Swap the values of `p` and `h`.
                    mstore(p, mload(h))
                    mstore(h, x)

                    p := l // Set the pivot slot to the left of the slice.
                    let e := sub(h, 0x20) // End of the partition.

                    // prettier-ignore
                    for { let j := l } iszero(gt(j, e)) { j := add(j, 0x20) } {
                        // Whenever a value less than the pivot value is 
                        // detected, move it to the left of the slice, 
                        // and advance the pivot slot.
                        if iszero(gt(mload(j), x)) {
                            let t := mload(p)
                            mstore(p, mload(j))
                            mstore(j, t)
                            p := add(p, 0x20)
                        }
                    }
                    // Swap back the values of `p` and `h`.
                    {
                        let t := mload(p)
                        mstore(p, x) // Restore the pivot value at the pivot slot.
                        mstore(h, t) // Store whatever was the replaced value at the end.
                    }
                    // If slice on left of pivot is non-empty, push onto stack.
                    {
                        let t := sub(p, 0x20)
                        // We can skip `mstore(stack, l)`.
                        mstore(add(stack, 0x20), t)
                        // `shl` 6 is equivalent to multiplying by `0x40`.
                        stack := add(stack, shl(6, gt(t, l)))
                    }
                    // If slice on right of pivot is non-empty, push onto stack.
                    {
                        let t := add(p, 0x20)
                        mstore(stack, t)
                        mstore(add(stack, 0x20), h)
                        // `shl` 6 is equivalent to multiplying by `0x40`.
                        stack := add(stack, shl(6, lt(t, h)))    
                    }
                }
            }
            mstore(a, n) // Restore the length of `a`.
        }
    }

    function sort(address[] memory a) internal pure {
        // As any address written to memory will have the upper 96 bits of the
        // word zeroized (as per Solidity spec), we can directly compare
        // these addresses as if they are whole uint256 words.
        uint256[] memory aCasted;
        assembly {
            aCasted := a
        }
        sort(aCasted);
    }

    function sortOriginal(
        uint256[] memory arr,
        int256 left,
        int256 right
    ) internal pure {
        int256 i = left;
        int256 j = right;
        if (i == j) return;
        uint256 pivot = arr[uint256(left + (right - left) / 2)];
        while (i <= j) {
            while (arr[uint256(i)] < pivot) {
                unchecked {
                    ++i;
                }
            }
            while (pivot < arr[uint256(j)]) {
                unchecked {
                    --j;
                }
            }
            if (i <= j) {
                (arr[uint256(i)], arr[uint256(j)]) = (arr[uint256(j)], arr[uint256(i)]);
                unchecked {
                    ++i;
                    --j;
                }
            }
        }
        if (left < j) sortOriginal(arr, left, j);
        if (i < right) sortOriginal(arr, i, right);
    }
}

Sort.t.sol

// SPDX-License-Identifier: Unlicense
pragma solidity >=0.8.0;

import "forge-std/Test.sol";
import {Sort} from "../Sort.sol";

contract SortTest is Test {
    function testSortChecksumed(uint256[] memory a) public {
        unchecked {
            vm.assume(a.length < 2048);
            uint256 checksum;
            for (uint256 i = 0; i < a.length; ++i) {
                checksum += a[i];
            }
            Sort.sort(a);
            uint256 checksumAfterSort;
            for (uint256 i = 0; i < a.length; ++i) {
                checksumAfterSort += a[i];
            }
            assertEq(checksum, checksumAfterSort);
            for (uint256 i = 1; i < a.length; ++i) {
                assertTrue(a[i - 1] <= a[i]);
            }
        }
    }

    function testSortDifferential(uint256[] memory a) public {
        unchecked {
            vm.assume(a.length < 128);
            // Make a copy of the `a` and perform insertion sort on it.
            uint256[] memory aCopy = new uint256[](a.length);
            for (uint256 i = 0; i < a.length; ++i) {
                aCopy[i] = a[i];
            }
            for (uint256 i = 1; i < aCopy.length; ++i) {
                uint256 key = aCopy[i];
                uint256 j = i;
                while (j != 0 && aCopy[j - 1] > key) {
                    aCopy[j] = aCopy[j - 1];
                    --j;
                }
                aCopy[j] = key;
            }
            Sort.sort(a);
            // Compare the results.
            for (uint256 i = 0; i < a.length; ++i) {
                assertEq(a[i], aCopy[i]);
            }
        }
    }

    function testSort(uint256[] memory a) public {
        unchecked {
            vm.assume(a.length < 2048);
            Sort.sort(a);
            for (uint256 i = 1; i < a.length; ++i) {
                assertTrue(a[i - 1] <= a[i]);
            }
        }
    }

    function testSortBasicCase() public {
        unchecked {
            uint256[] memory a = new uint256[](2);
            a[0] = 3;
            a[1] = 0;
            Sort.sort(a);
            for (uint256 i = 1; i < a.length; ++i) {
                assertTrue(a[i - 1] <= a[i]);
            }
        }
    }

    function testSortPsuedorandom() public {
        unchecked {
            uint256[] memory a = new uint256[](100);
            uint256 lcg = 123456789;
            for (uint256 i; i < a.length; ++i) {
                a[i] = lcg;
                lcg = (lcg * 1664525 + 1013904223) & 0xFFFFFFFF;
            }
            Sort.sort(a);
            for (uint256 i = 1; i < a.length; ++i) {
                assertTrue(a[i - 1] <= a[i]);
            }    
        }
    }

    function testSortSorted() public {
        unchecked {
            uint256[] memory a = new uint256[](100);
            for (uint256 i; i < a.length; ++i) {
                a[i] = i;
            }
            Sort.sort(a);
            for (uint256 i = 1; i < a.length; ++i) {
                assertTrue(a[i - 1] <= a[i]);
            }    
        }
    }

    function testSortReversed() public {
        unchecked {
            uint256[] memory a = new uint256[](100);
            for (uint256 i; i < a.length; ++i) {
                a[i] = 999 - i;
            }
            Sort.sort(a);
            for (uint256 i = 1; i < a.length; ++i) {
                assertTrue(a[i - 1] <= a[i]);
            }    
        }
    }

    function testSortAddressesPsuedorandomBrutalizeUpperBits() public {
        unchecked {
            address[] memory a = new address[](100);
            uint256 lcg = 123456789;
            for (uint256 i; i < a.length; ++i) {
                address addr = address(uint160(lcg));
                lcg = (lcg * 1664525 + 1013904223) & 0xFFFFFFFF;
                assembly {
                    addr := or(addr, shl(160, lcg))
                }
                a[i] = addr;
                lcg = (lcg * 1664525 + 1013904223) & 0xFFFFFFFF;
            }
            Sort.sort(a);
            for (uint256 i = 1; i < a.length; ++i) {
                assertTrue(a[i - 1] <= a[i]);
            }    
        }
    }

    function testSortAddressesPsuedorandom() public {
        unchecked {
            address[] memory a = new address[](100);
            uint256 lcg = 123456789;
            for (uint256 i; i < a.length; ++i) {
                a[i] = address(uint160(lcg));
                lcg = (lcg * 1664525 + 1013904223) & 0xFFFFFFFF;
            }
            Sort.sort(a);
            for (uint256 i = 1; i < a.length; ++i) {
                assertTrue(a[i - 1] <= a[i]);
            }    
        }
    }

    function testSortAddressesSorted() public {
        unchecked {
            address[] memory a = new address[](100);
            for (uint256 i; i < a.length; ++i) {
                a[i] = address(uint160(i));
            }
            Sort.sort(a);
            for (uint256 i = 1; i < a.length; ++i) {
                assertTrue(a[i - 1] <= a[i]);
            }    
        }
    }

    function testSortAddressesReversed() public {
        unchecked {
            address[] memory a = new address[](100);
            for (uint256 i; i < a.length; ++i) {
                a[i] = address(uint160(999 - i));
            }
            Sort.sort(a);
            for (uint256 i = 1; i < a.length; ++i) {
                assertTrue(a[i - 1] <= a[i]);
            }    
        }
    }

    function testSortOriginalPsuedorandom() public {
        unchecked {
            uint256[] memory a = new uint256[](100);
            uint256 lcg = 123456789;
            for (uint256 i; i < a.length; ++i) {
                a[i] = lcg;
                lcg = (lcg * 1664525 + 1013904223) & 0xFFFFFFFF;
            }
            Sort.sortOriginal(a, 0, int256(a.length - 1));
            for (uint256 i = 1; i < a.length; ++i) {
                assertTrue(a[i - 1] <= a[i]);
            }    
        }
    }

    function testSortOriginalSorted() public {
        unchecked {
            uint256[] memory a = new uint256[](100);
            for (uint256 i; i < a.length; ++i) {
                a[i] = i;
            }
            Sort.sortOriginal(a, 0, int256(a.length - 1));
            for (uint256 i = 1; i < a.length; ++i) {
                assertTrue(a[i - 1] <= a[i]);
            }    
        }
    }

    function testSortOriginalReversed() public {
        unchecked {
            uint256[] memory a = new uint256[](100);
            for (uint256 i; i < a.length; ++i) {
                a[i] = 999 - i;
            }
            Sort.sortOriginal(a, 0, int256(a.length - 1));
            for (uint256 i = 1; i < a.length; ++i) {
                assertTrue(a[i - 1] <= a[i]);
            }    
        }
    }
}

It's not relevant to sort.

for (uint256 i = 1; i < a.length; ++i) { assertTrue(a[i - 1] <= a[i]); }
You can place above code in one function and call whenever you need. It's just suggestion for redundant code.😀

Oo okok.