# Submission d8a9cfdb...

Challenge Integer sorting wicketh.eth 2018-34-28 287610
``````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  simply sorted input
// Yes repeated but sorted input

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

let temp
let scale
let i

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

// 80 * 32 = 2560  = size of bucket table

// Check for input that is already sorted
i := 0x64
l0:
jumpi(l0, lt(i, calldatasize))

// First pass: find upper bound to values and compute scaling factor
scale := 0
i := 0x44
l1:
jumpi(l1, lt(i, calldatasize))

// Second pass: count buckets (in multipes of 32)
i := 0x44
l2:
jumpi(l2, lt(i, calldatasize))
temp := 2560 // Include write offset
i := 0x00
l3:
mstore(i, temp)
jumpi(l3, lt(i, 2560))

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

// Fourth pass: sort buckets
i := 0x20
l5:
jumpi(l5, lt(i, 2560))
jump(l5e)
l5n:
jumpi(l5, lt(i, 2560))
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(2560, 0x40), 0x20)