Submission 4015ca76...
/**
* 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))
}
}
}
}