Submission 3eef71c1...

ChallengeInteger sorting
Submitter0x1dba1131000664b...
Submitted at2018-58-26
Gas used592766
/**
 * This file is part of the 1st Solidity Gas Golfing Contest.
 *
 * This work is licensed under Creative Commons Attribution ShareAlike 3.0.
 * https://creativecommons.org/licenses/by-sa/3.0/
 * Author: Jordi Baylina
 */

pragma solidity 0.4.24;

contract Sort {
    /**
     * @dev Sorts a list of integers in ascending order.
     *
     * The input list may be of any length.
     *
     * @param input The list of integers to sort.
     * @return The sorted list.
     */

    struct List {
        uint start;
        uint end;
    }
    function sort(uint[]  input) public pure returns(uint[] aux) {
        uint il = input.length;
        if (il<2) return input;
        aux = new uint[](input.length);

        uint[] memory listEnd = new uint[](input.length);
        uint[] memory src = input;
        uint[] memory dst = aux;

        uint nlists = 0;

        assembly {

/*
        uint last = input[0];
        for (uint i=1; i<il; i++) {
            uint act = input[i];
            if (last > act) {
                listEnd[nlists++] = i;
            }
            last = act;
        }
        listEnd[nlists++] = il;
*/

            let ple := add(listEnd, 32)
            for {
                let pl := add(input,32)
                let last := mload(pl)
                let i := 1
                pl := add(pl,32)
            } lt(i,il) {
                i := add(i,1)
                pl := add(pl, 32)
            }
            {
                let act := mload(pl)
                if lt(act, last) {
                    mstore(ple, i)
                    ple := add(ple, 32)
                    nlists := add(nlists,1)
                }
                last := act
            }
            mstore(ple, il)
            nlists := add(nlists,1)


/*
        while (nlists>1) {
            for (uint l=0; l<nlists; l+=2) {
                if (l+1 == nlists) {
                    copyList(src, dst, listEnd[l-1], il);
                    listEnd[l/2] = il;
                } else {
                    joinList(src, dst, l==0 ? 0 : listEnd[l-1], listEnd[l], listEnd[l+1]);
                    listEnd[l/2] = listEnd[l+1];
                }
            }

            nlists = (nlists+1)/2;

            (src, dst) = (dst, src);
        }
*/

            for {} gt(nlists, 1) { } {
                for {
                    let l:=0
                    let outp := add(listEnd, 32)
                } lt(l, nlists) {
                    l:=add(l,2)
                    outp := add(outp,32)
                } {
                    switch eq(add(l,1), nlists)
                    case 1 {
                        let le_min1 := mload(add(listEnd, mul(l,32)))
                        copyList(src, dst, le_min1, il)
                        mstore(outp, il)
                    }
                    default {
                        let le_min1 := mload(add(listEnd, mul(l,32)))
                        let le_0 := mload(add(listEnd, add(32, mul(l,32))))
                        let le_plus1 := mload(add(listEnd, add(64, mul(l,32))))
                        if eq(l,0) {
                            le_min1 := 0
                        }
                        joinList(src, dst, le_min1, le_0, le_plus1)
                        mstore(outp, le_plus1)
                    }
                }
                nlists := div(add(nlists, 1),2)

                let aux := src
                src := dst
                dst := aux
            }



/*
    function copyList(uint[] memory src, uint[] memory dst, uint p1, uint e1) pure internal {

        uint o=p1;
        while (p1<e1) dst[o++] = src[p1++];
    }
*/

            function copyList (src, dst, p1, e1) {
                for {
                    let ofs := add(32, mul(p1, 32) )
                    let inp := add(src, ofs)
                    let out := add(dst, ofs)
                    let end :=  add(src, add(32, mul(e1, 32) ))
                } lt (inp, end) {
                    inp := add(inp, 32)
                    out := add(out,32)
                } {
                    mstore(out, mload(inp))
                }
            }

/*
    function joinList(uint[] memory src, uint[] memory dst, uint p1, uint p2, uint e2) pure internal {
        uint e1 = p2;
        uint o=p1;

        while ((p2<e2)&&(p1<e1)) {
            dst[o++] = (src[p1]<src[p2]) ? src[p1++] : src[p2++];
        }
        while (p1<e1) dst[o++] = src[p1++];
        while (p2<e2) dst[o++] = src[p2++];
    }
*/
            function joinList(src, dst, p1, p2, e2) {
                let inp1 :=  add(src, add(32, mul(p1, 32) ))
                let inp2 :=  add(src, add(32, mul(p2, 32) ))
                let out := add(dst, add(32, mul(p1, 32) ))
                let ine1 := inp2
                let ine2 :=  add(src, add(32, mul(e2, 32) ))
                for {
                } and(lt(inp1, ine1), lt(inp2, ine2))
                {
                    out := add(out,32)
                } {
                    let a := mload(inp1)
                    let b := mload(inp2)
                    switch lt(a,b)
                    case 0 {
                        mstore(out,b)
                        inp2 := add(inp2,32)
                    }
                    default {
                        mstore(out,a)
                        inp1 := add(inp1,32)
                    }
                }
                for {} lt(inp1, ine1) {
                    inp1 := add(inp1, 32)
                    out := add(out, 32)
                } {
                    mstore(out, mload(inp1))
                }
                for {} lt(inp2, ine2) {
                    inp2 := add(inp2, 32)
                    out := add(out, 32)
                } {
                    mstore(out, mload(inp2))
                }
            }


        }

        return src;
    }

}