Submission 585f4f87...

ChallengeInteger sorting
Submitterzac.creditmint.eth
Submitted at2018-46-27
Gas used254430
/**
 * 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/
 */

pragma solidity ^0.4.23;

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.
     */

    function sort(uint[] input) external view returns(uint[]) {
        assembly {
            calldatacopy(0, 0x04, calldatasize)
            if eq(calldatasize, 0x44) {
                return(0x00, 0x40)
            }
            let it := 0x60
            let size := sub(calldatasize, 0x24)
            let end := add(size, 0x20)
            let prev := mload(0x40)
            check_if_perfect_start:
                jumpi(check_if_perfect_skip, gt(prev, mload(it)))
                prev := mload(it)
                it := add(it, 0x20)
                jumpi(check_if_perfect_start, lt(it, end))
                return(0x00, add(end, 0x40)) // hey it's perfect!
            check_if_perfect_skip:
                it := 0x60
                prev := mload(0x40)
            check_if_reverse_start:
                jumpi(check_if_reverse_skip, lt(prev, mload(it)))
                prev := mload(it)
                it := add(it, 0x20)
                jumpi(check_if_reverse_start, lt(it, end))
                it := size
                end := msize
                for {} gt(it, 0x20) {} {
                    mstore(msize, mload(it))
                    it := sub(it, 0x20)
                }
                mstore(sub(end, 0x20), mload(0x20))
                mstore(sub(end, 0x40), 0x20)
                return(sub(end, 0x40), add(size, 0x60)) // hey it's reversed!
            check_if_reverse_skip:

            0 not 0 not         // 0 0
            0x40 size           // p_high p_low 0 0

            asm_evaluate_stack:
                dup1 dup3 lt asm_partition jumpi
                pop pop
                dup1 0 not eq asm_finish_sort jumpi
                asm_evaluate_stack jump
            asm_partition:
    // partition
            // 0x20 0x20 dup4 dup4 sub div 0x30644e72e131a029b85045b68181585d97816a916871ca8d3c208c16d87cfd47 gas mulmod mul dup3 add
            dup2
            mload               // p p_high p_low
            0x20 dup4 sub       // i p p_high p_low
            dup3 0x20 add       // j i p p_high p_low
            asm_increase_i jump

            asm_partition_swap:
                                // j i p p_high p_low
                dup1 mload      // vj j i p p_high p_low
                dup3 mload      // vi vj j i p p_high p_low
                dup3 mstore     // vj j i p p_high p_low
                dup3 mstore     // j i p p_high p_low

            asm_increase_i:
                swap1 0x20 add swap1 // hmmm
                dup3 dup3 mload lt asm_increase_i jumpi
            asm_decrease_j:
                0x20 swap1 sub  // j i p p_high p_low
                dup3 dup2 mload gt asm_decrease_j jumpi
            dup1 dup3 lt asm_partition_swap jumpi

            swap2 pop pop       // p' p_high p_low
            dup1 0x20 add       // p'' p' p_high p_low
            swap3 swap1         // p' p_low p_high p''

            asm_evaluate_stack jump

            asm_finish_sort:
            0x04 calldatasize sub 0x00 return
            pop pop pop pop
            // hoareQuickSort(0x40, size)
            // return(0x00, add(end, 0x40))

            function hoareQuickSort(p_low, p_high) {
                if lt(p_low, p_high) {
                    let pi := hoarePartition(p_low, p_high)
                    hoareQuickSort(p_low, pi)
                    hoareQuickSort(add(pi, 0x20), p_high)
                }
            }
            function hoarePartition(p_low, p_high) -> j {
                let factor := add(p_low, mul(mulmod(gas, 0x30644e72e131a029b85045b68181585d97816a916871ca8d3c208c16d87cfd47, div(sub(p_high, p_low), 0x20)), 0x20))
                let pivot := mload(factor)
                let i := sub(p_low, 0x20)
                j := add(p_high, 0x20)
                let t
                jump(partition_start)
                partition_swap:
                    t := mload(j)
                    mstore(j, mload(i))
                    mstore(i, t)
                partition_start:
                    increase_i:
                        i := add(i, 0x20)
                        jumpi(increase_i, lt(mload(i), pivot))
                    decrease_j:
                        j := sub(j, 0x20)
                        jumpi(decrease_j, gt(mload(j), pivot))
                    jumpi(partition_swap, lt(i, j))
            }
        }
    }
}