Submission 4015ca76...

Challenge	Integer sorting
Submitter	zac.creditmint.eth
Submitted at	2018-53-27
Gas used	374224

/**
 * 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)
            let current
            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
            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))
                revert(0x00, 0x00)
            check_if_reverse_skip: */

            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))
            }
        }
    }
}