Submission 4b49aeec...

ChallengeInteger sorting
Submitter0xec3281124d4c2fc...
Submitted at2018-21-08
Gas used528351
pragma solidity 0.4.24;


contract Sort {

    function sort(uint[] input) public pure returns(uint[]) {
        if (input.length == 0)
            return;
        uint arrayStart = 0;
        assembly {
            arrayStart := add(input, 0x20)
        }
        sort(arrayStart, input, 0, (input.length-1)*0x20);
        return input;
    }

    function sort(uint arrayStart, uint[] arr, uint left, uint right) internal pure {
        uint i=left;
        uint j=right;
        uint pivot;

        assembly {
            pivot := mload(add(arrayStart, mul(0x20, div(add(left, div(sub(right, left), 2)),0x20))))
            for {} iszero(gt(i, j)) {} {
                for {} lt(mload(add(arrayStart, i)), pivot) {} {
                    i := add(i, 0x20)
                }

                for {} lt(pivot, mload(add(arrayStart, j))) {} {
                    j := sub(j, 0x20)
                }
                switch gt(i, j)
                case 0 {
                    let iLoc := add(arrayStart, i)
                    let jLoc := add(arrayStart, j)
                    let temp := mload(iLoc)
                    mstore(iLoc, mload(jLoc))
                    mstore(jLoc, temp)
                    i := add(i, 0x20)
                    j := sub(j, 0x20)
                }
            }
        }
        if (left < j)
            sort(arrayStart, arr, left, j);
        if (i < right)
            sort(arrayStart, arr, i, right);
    }
}