# Submission 1dc18a1d...

Challenge Integer sorting wicketh.eth 2018-00-28 181372
``````pragma solidity ^0.4.23;

contract Sort {

function () external payable { assembly {

// function sort(uint[] input) external payable returns(uint[]) { assembly {

// @author Remco Bloemen <[email protected]>

// No  unrepeated sorted input
// Yes repeated sorted input
// No  unrepeated reverse sorted input
// Yes repeated reverse sorted input

mstore(0x40, 0) // Set all memory to zero

let temp1
let temp2
let scale
let i

// Special case for zero or one value
jumpi(trivial, lt(calldatasize, 0x84))

// Size of bucket table:
//                                      Competition
//  60 * 32 = 1920    gas: 337644        208971
//  80 * 32 = 2560    gas: 323985        194330
// 100 * 32 = 3200    gas: 321639        193251
// 110 * 32 = 3520    gas: 318570        190720
// 120 * 32 = 3840    gas: 315349        186302
// 130 * 32 = 4160    gas: 314771        188363
// 140 * 32 = 4480    gas: 314657        186329
// 160 * 32 = 5120    gas: 317469        189141
// 256 *  1 = 256

// First pass (input):
// * find upper bound to values
// * check for sorted input
// * check for reverse sorted input
scale := temp1
i := 0x64
scale := or(scale, temp2)
temp1 := temp2
jumpi(l1, lt(i, calldatasize))

// max(input size) = 299

// Compute scaling factor

// Second pass (input): count buckets (in multipes of 32)
i := 0x44
l2:
jumpi(l2, lt(i, calldatasize))

// Third pass (buckets): running total in buckets

// Fourth pass (input): move to buckets
i := 0x44
l4:
jumpi(l4, lt(i, calldatasize))

// Fifth pass (buckets): sort buckets
i := 0x20
l5:
jumpi(l5, lt(i, 3840))
jump(l5e)
l5n:
jumpi(l5, lt(i, 3840))
l5e:
jump(done)

l5s:

function sort(lo, hi) {

let lolo := lo
let hihi := hi
let d := sub(hi, lo)

if lt(d, 96) {

// Optimize for two
jumpi(three, gt(d, 32))
{
jumpi(end, gt(b, a))
mstore(lo, b)
mstore(hi, a)
end:
}
jump(ret)

// Optimize for three
three:
{
jumpi(case1, gt(b, a))
a
b
=: a
=: b
case1:
jumpi(case3, gt(c, b))
b
c
=: b
=: c
jumpi(case3, gt(b, a))
a
b
=: a
=: b
case3:
mstore(lo, a)
mstore(hi, c)
}
jump(ret)
}

// Partition
{
let pivot
let lov
let hiv

// Compute pivot value
0x0fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe0
)

loop:
jumpi(loend, iszero(lt(lov, pivot)))
loloop:
jumpi(loloop, lt(lov, pivot))
loend:
jumpi(hiend, iszero(gt(hiv, pivot)))
hiloop:
hi := sub(hi, 32)
jumpi(hiloop, gt(hiv, pivot))
hiend:
jumpi(end, iszero(lt(lo, hi)))
mstore(lo, hiv)
mstore(hi, lov)
hi := sub(hi, 32)
jump(loop)

end:
lo := hi
}

// Recurse
jumpi(sorthi, eq(lolo, lo))
sort(lolo, lo)
sorthi:
jumpi(ret, eq(hi, hihi))
sort(hi, hihi)
ret:
}

done:
mstore(sub(3840, 0x40), 0x20)
return(sub(3840, 0x40), sub(calldatasize, 4))

trivial:
calldatacopy(0, 4, calldatasize)
return(0, sub(calldatasize, 4))

reverse:
calldatacopy(0, 4, 0x40)
i := 0x44
temp1 := sub(calldatasize, 36)

lr: