Submission cfb056a8...

ChallengeInteger sorting
Submitter0x6b9205614d2523d...
Submitted at2018-05-08
Gas used585876
pragma solidity 0.4.24;


contract Sort {

    function sort(uint[] input) public pure returns(uint[]) {
        if (input.length == 0)
            return;
        sort(input, 0, input.length - 1);
        return input;
    }

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

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

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