Submission b89fff26...

ChallengeInteger sorting
Submitterricmoo.firefly.eth
Submitted at2018-00-29
Gas used525934
pragma solidity 0.4.24;

contract Sort {
    function sort(uint[] /* input */) public pure returns(uint[]) {

        assembly {
            let tmp := 0
            let a := 0
            let b := 0
            let done := 0

            // @TODO: Mulitply by 32 soon! 
            let length := calldataload(36)

            let output := mload(0x40)

            // Trivial case; 0 or 1 elements; already sorted
            if lt(length, 2) {
                tmp := sub(calldatasize, 4)
                calldatacopy(output, 4, tmp)
                return(output, tmp)
            }

            // Store the dynlink0 and length for the output
            mstore(output, 32)
            mstore(add(output, 32), length)
            let input := add(output, 64)

            // Convert length to bytes
            length := mul(32, length)

            // tmp => value
            // a   => lastValue
            // b   => count of out-of-order elements
            let io := 68
            let eo := add(io, length)
            for {} lt(io, eo) {} {
                tmp := calldataload(io)
                b := add(b, gt(a, tmp))
                a := tmp
                // @TODO: May be able to make inpur or io an offset of the other?
                mstore(input, tmp)
                io := add(io, 32)
                input := add(input, 32)
            }

            // No elements out-of-order; already sorted
            if iszero(b) {
                return(output, sub(calldatasize, 4))
            }

            input := add(output, 64)

            // If over 25% of the elements are out of order, reverse the list
            a := mul(32, b)
            if lt(sub(length, a), div(length, 8)) {
                io := input
                let jo := add(input, sub(length, 32))
                for {} lt(io, jo) {} {
                    tmp := mload(io)
                    mstore(io, mload(jo))
                    mstore(jo, tmp)
                    io := add(io, 32)
                    jo := sub(jo, 32)
                }
                b := sub(calldataload(36), b)
            }

            // QuickSort
            // See: https://www.geeksforgeeks.org/iterative-quick-sort/

            // More than 8 elements out of order; quicksort-ish
            if gt(b, 8) {

                /// Quicksort

                let loo := input
                let hio := add(input, sub(length, 32))
                let stackTop := add(output, add(length, 64))
                let stackBase := stackTop

                let jo := 0

                done := 1
                for {} done {} {

                    // Choose a pivot
                    tmp := mload(and(div(add(loo, hio), 2), 0xffffffffe0))

                    /// Partition

                    io := sub(loo, 32)
                    jo := add(hio, 32)
                    //done := 1
                    for {} done {} {

                        // Not done
                        done := 1
                        for {} done {} {
                            io := add(io, 32)
                            a := mload(io)
                            done := lt(a, tmp)
                        }

                        // Not done
                        done := 1
                        for {} done {} {
                            jo := sub(jo, 32)
                            b := mload(jo)
                            done := gt(b, tmp)
                        }

                        if lt(io, jo) {
                            mstore(io, b)
                            mstore(jo, a)
                            done := 1
                        }
                    }

                    //done := 0

                    /// Pick new lo and hi

                    //if (j > lo):
                    //let cond := gt(jo, loo)
                    //if (j > lo + 8):
                    let cond := gt(jo, add(loo, 256))
                    if cond {

                        //if (j + 1 < hi):
                        //if (j + 1 + 8 < hi):
                        //if lt(add(jo, 32), hio)
                        if lt(add(jo, 288), hio) {
                            mstore(stackTop, add(jo, 32))
                            stackTop := add(stackTop, 32)
                            mstore(stackTop, hio)
                            stackTop := add(stackTop, 32)
                        }
                        hio := jo
                        done := 1
                    }

                    if iszero(cond) {

                    // else if (j + 1 < hi):
                    // else if (j + 1 + 8  < hi):
                        //cond := lt(add(jo, 32), hio)
                        cond := lt(add(jo, 288), hio)
                        if cond {
                            loo := add(jo, 32)
                            done := 1
                        }

                        if iszero(cond) {

                            // else if (stackTop != 0):
                            //cond := eq(stackTop, stackBase)
                            //if iszero(cond) {
                            if gt(stackTop, stackBase) {
                                stackTop := sub(stackTop, 32)
                                hio := mload(stackTop)
                                stackTop := sub(stackTop, 32)
                                loo := mload(stackTop)
                                done := 1
                            }
                        }
                    }
                }
            }

            // Linear Insertion Sort
            // See: https://en.wikipedia.org/wiki/Insertion_sort

            //let inputBase := add(input, 32)
            // for (var i = 0; i < length; i++):
            io := add(input, 32)
            let ie := add(input, length)
            for {} lt(io, ie) {} {

                // a = input[i]
                // j = i
                let tmp3 := mload(io)
                let jo := io

                // while (j != 0):
                done := 0
                for { } iszero(done) { } {
                    if eq(jo, input) { done := 1 }
                    if iszero(done) {
                        // b = input[j - 1]
                        let tmp2 := mload(sub(jo, 32))

                        // if (b > a): input[j--] = b
                        done := 1
                        if gt(tmp2, tmp3) {
                            mstore(jo, tmp2)
                            jo := sub(jo, 32)
                            done := 0
                        }
                    }
                }

                // input[j] = a
                mstore(jo, tmp3)
                io := add(io, 32)
            }

            return(output, add(length, 64))
        }
    }
}