Submission 2570c8f9...

ChallengeInteger sorting
Submitterwicketh.eth
Submitted at2018-45-11
Gas used345344
pragma solidity ^0.4.23;

contract Sort {
    
    function () external payable { assembly {
        
        // @author Remco Bloemen <[email protected]>
        
        // Copy input to memory
        calldatacopy(0, 4, calldatasize)
        
        // Special case for zero or one value
        jumpi(done, lt(calldatasize, 0x84))
        
        // Recursively sort
        sort(0x40, sub(calldatasize, 0x24))
        function sort(lo, hi) {
            
            let lolo := lo
            let hihi := hi
            let d := sub(hi, lo)
            
            if lt(d, 96) {
                
                // Optimize for two
                if eq(d, 32) {
                    {
                        let a := mload(lo)
                        let b := mload(hi)
                        if lt(b, a) {
                            mstore(lo, b)
                            mstore(hi, a)
                        }
                    }
                    jump(ret)
                }
                
                // Optimize for three
                //if eq(sub(hi, lo), 64) {
                    {
                        let a := mload(lo)
                        let b := mload(add(lo, 32))
                        let c := mload(hi)
                        if lt(b, a) {
                            a
                            b
                            =: a
                            =: b
                        }
                        if lt(c, b) {
                            b
                            c
                            =: b
                            =: c
                            if lt(b, a) {
                                a
                                b
                                =: a
                                =: b
                            }
                        }
                        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
            
        sortlo:
            jumpi(sorthi, eq(lolo, lo))
            sort(lolo, lo)
        
        sorthi:
            jumpi(ret, eq(hi, hihi))
            sort(hi, hihi)
            
        ret:
        }
        
        
    done:
        return(0, sub(calldatasize, 4))
    }}
}