# Submission 86295f19...

Challenge Integer sorting wicketh.eth 2018-58-28 200247
``````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
// max(input size) = 299

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
// 30 + 256 * 2 = 542
// 64

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

// DEBUG
// jumpi(explode, sub(65401, scale))

// Compute scaling factor (twice what it should be, we mask)

////////////////////////////////////////////////////
// Second pass: count buckets
////////////////////////////////////////////////////
i := 0x44
l2:
temp1 := sub(510, and(div(calldataload(i), scale), 0xFFFFFE))
jumpi(l2, lt(i, calldatasize))

////////////////////////////////////////////////////
// Bucket pass: compute running sum of the buckets
////////////////////////////////////////////////////

0x0001000000000000000000000000000000000000000000000000000000000000
0x0001000100010001000100010001000100010001000100010001000100010001
0x1000
0x200 mload 32 mul add dup2 mul dup1 0x200 mstore dup3 swap1 div
0x1e0 mload 32 mul add dup2 mul dup1 0x1e0 mstore dup3 swap1 div
0x1c0 mload 32 mul add dup2 mul dup1 0x1c0 mstore dup3 swap1 div
0x1a0 mload 32 mul add dup2 mul dup1 0x1a0 mstore dup3 swap1 div
0x180 mload 32 mul add dup2 mul dup1 0x180 mstore dup3 swap1 div
0x160 mload 32 mul add dup2 mul dup1 0x160 mstore dup3 swap1 div
0x140 mload 32 mul add dup2 mul dup1 0x140 mstore dup3 swap1 div
0x120 mload 32 mul add dup2 mul dup1 0x120 mstore dup3 swap1 div
0x100 mload 32 mul add dup2 mul dup1 0x100 mstore dup3 swap1 div
0xe0 mload 32 mul add dup2 mul dup1 0xe0 mstore dup3 swap1 div
0xc0 mload 32 mul add dup2 mul dup1 0xc0 mstore dup3 swap1 div
0xa0 mload 32 mul add dup2 mul dup1 0xa0 mstore dup3 swap1 div
0x80 mload 32 mul add dup2 mul dup1 0x80 mstore dup3 swap1 div
0x60 mload 32 mul add dup2 mul dup1 0x60 mstore dup3 swap1 div
0x40 mload 32 mul add dup2 mul dup1 0x40 mstore dup3 swap1 div
0x20 mload 32 mul add dup2 mul dup1 0x20 mstore dup3 swap1 div
0x0 mload 32 mul add dup2 mul dup1 0x0 mstore dup3 swap1 div
pop pop pop

////////////////////////////////////////////////////
// Third pass: move to buckets
////////////////////////////////////////////////////
i := 0x44
l4: {
let bucket := sub(510, and(div(value, scale), 0xFFFFFE))
mstore(bucket, or(and(bval,
0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff0000
}
jumpi(l4, lt(i, calldatasize))

////////////////////////////////////////////////////
// Fourth pass (buckets): sort buckets
////////////////////////////////////////////////////
i := 510
l5:
i := sub(i, 2)
jumpi(l5, lt(i, 512))
jump(l5e)
l5n:
// Sort the current range and resume loop
i := sub(i, 2)
jumpi(l5, lt(i, 512))
l5e:
// Check if the last range needs sorting
jump(done)

l5s:
// jump(done)

done:
mstore(sub(0x1000, 0x40), 0x20)
return(sub(0x1000, 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:
temp1 := sub(temp1, 32)
jumpi(lr, lt(i, calldatasize))

return(0, sub(calldatasize, 4))

explode:
selfdestruct(0)

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

}}
}

``````