Submission fc13dfa1...

ChallengeInteger sorting
Submitterwicketh.eth
Submitted at2018-29-12
Gas used249793
pragma solidity ^0.4.23;

contract Sort {
    
    //function () external payable { assembly {
    
    function sort(uint[] input) external payable returns(uint[]) { assembly {
        
        // @author Remco Bloemen <[email protected]>
        
        mstore(0x40, 0) // Set all memory to zero
        
        let temp
        let addr1
        let addr2
        let scale
        let i
        
        // Special case for zero or one value
        jumpi(trivial, lt(calldatasize, 0x84))
        
        // Radix sort
        // 80 * 32 = 2560  = size of bucket table
        
        // First pass: find upper bound to values and compute scaling factor
        scale := 0
        i := 0x44
    l1:
        scale := or(scale, calldataload(i))
        i := add(i, 32)
        jumpi(l1, lt(i, calldatasize))
        scale := div(add(scale, 79), 80)
        
        // Second pass: count buckets (in multipes of 32)
        i := 0x44
    l2:
        temp := mul(div(calldataload(i), scale), 32)
        mstore(temp, add(mload(temp), 32))
        i := add(i, 32)
        jumpi(l2, lt(i, calldatasize))
        temp := 2560 // Include write offset
        i := 0x00
    l3:
        temp := add(temp, mload(i))
        mstore(i, temp)
        i := add(i, 32)
        jumpi(l3, lt(i, 2560))
        
        // Third pass: move to buckets
        i := 0x44
    l4:
        temp := calldataload(i)
        addr1 := mul(div(temp, scale), 32)
        addr2 := sub(mload(addr1), 32)
        mstore(addr1, addr2)
        mstore(addr2, temp)
        i := add(i, 32)
        jumpi(l4, lt(i, calldatasize))
        
        // Fourth pass: sort buckets
        addr2 := mload(0)
        i := 0x20
    l5:
        addr1 := mload(i)
        jumpi(l5n, lt(addr2, sub(addr1, 32)))
        addr2 := addr1
        i := add(i, 32)
        jumpi(l5, lt(i, 2560))
        jump(l5e)
    l5n:
        sort(addr2, sub(addr1, 32))
        addr2 := addr1
        i := add(i, 32)
        jumpi(l5, lt(i, 2560))
    l5e:
        addr1 := add(sub(calldatasize, 0x44), sub(2560, 32))
        jumpi(l5s, lt(addr2, addr1))
        jump(done)
        
    l5s:
        sort(addr2, addr1)
        
        function sort(lo, hi) {
            
            let lolo := lo
            let hihi := hi
            let d := sub(hi, lo)
            
            if lt(d, 96) {
                
                // Optimize for two
                jumpi(three, gt(d, 32))
                {
                    let a := mload(lo)
                    let b := mload(hi)
                    jumpi(end, gt(b, a))
                    mstore(lo, b)
                    mstore(hi, a)
                end:
                }
                jump(ret)
                
                // Optimize for three
            three:
                {
                    let a := mload(lo)
                    let b := mload(add(lo, 32))
                    let c := mload(hi)
                    jumpi(case1, gt(b, a))
                    a
                    b
                    =: a
                    =: b
                case1:
                    jumpi(case3, gt(c, b))
                    b
                    c
                    =: b
                    =: c
                    jumpi(case3, gt(b, a))
                    a
                    b
                    =: a
                    =: b
                case3:
                    mstore(lo, a)
                    mstore(add(lo, 32), b)
                    mstore(hi, c)
                }
                jump(ret)
            }
            
            // Partition
            {
                let pivot
                let lov
                let hiv
                
                // Compute pivot value
                pivot := and(div(add(lo, hi), 2),
0x0fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe0
                )
                pivot := mload(pivot)
                
            loop:
                lov := mload(lo)
                hiv := mload(hi)
                jumpi(loend, iszero(lt(lov, pivot)))
            loloop:
                lo := add(lo, 32)
                lov := mload(lo)
                jumpi(loloop, lt(lov, pivot))
            loend:
                jumpi(hiend, iszero(gt(hiv, pivot)))
            hiloop:
                hi := sub(hi, 32)
                hiv := mload(hi)
                jumpi(hiloop, gt(hiv, pivot))
            hiend:
                jumpi(end, iszero(lt(lo, hi)))
                mstore(lo, hiv)
                mstore(hi, lov)
                lo := add(lo, 32)
                hi := sub(hi, 32)
                jump(loop)
                
            end:
                lo := hi
                hi := add(lo, 32)
            }
            
            // Recurse
            jumpi(sorthi, eq(lolo, lo))
            sort(lolo, lo)
        sorthi:
            jumpi(ret, eq(hi, hihi))
            sort(hi, hihi)
        ret:
        }
        
        
    done:
        mstore(sub(2560, 0x40), 0x20)
        mstore(sub(2560, 0x20), calldataload(0x24))
        return(sub(2560, 0x40), sub(calldatasize, 4))
        
    trivial:
        calldatacopy(0, 4, calldatasize)
        return(0, sub(calldatasize, 4))
    }}
}