# Submission 5807d6e8...

Challenge Integer sorting wicketh.eth 2018-10-29 100539
``````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:
//  80 * 32 = 2560    gas:
// 100 * 32 = 3200    gas:
// 110 * 32 = 3520    gas: 240064       111292
// 120 * 32 = 3840    gas: 239759       110727
// 130 * 32 = 4160    gas: 239740       110853
// 140 * 32 = 4480    gas: 240168
// 160 * 32 = 5120    gas:
// 256 *  1 = 256

////////////////////////////////////////////////////
// First pass
////////////////////////////////////////////////////
// * find upper bound to values
// * check for sorted input
// * check for reverse sorted input
scale := temp1
i := 0x64
l1_equal: // All entries up untill i are the same
jumpi(l1_equal, and(lt(i, 0xE4), eq(temp1, temp2)))
jumpi(trivial, eq(i, 0xE4))
l1_neq:
jumpi(l1_reverse, gt(temp1, temp2))
scale := temp2
l1_forward:
temp1 := temp2
scale := or(scale, temp2)
jumpi(l1_forward, and(lt(i, 0xE4), lt(temp1, add(temp2, 1))))
jumpi(trivial, eq(i, 0xE4))
jump(l1)
l1_reverse:
temp1 := temp2
scale := or(scale, temp2)
jumpi(l1_reverse, and(lt(i, 0xE4), lt(temp2, add(temp1, 1))))
jumpi(reverse, eq(i, 0xE4))
l1:
jumpi(l1, lt(i, calldatasize))

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

///////////////////////////////////////////////////
// Second pass (input): count buckets (in multipes of 32)
///////////////////////////////////////////////////
0x44
l2: // Stack: i
// temp1 := mul(div(calldataload(i), scale), 32)
dup1 scale swap1 calldataload div 32 mul
// jumpi(l2, lt(i, calldatasize))
dup1 calldatasize gt l2 jumpi
pop

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

///////////////////////////////////////////////////
// Fourth pass (input): move to buckets
///////////////////////////////////////////////////
0x44
l4:
// addr1 := mul(div(temp1, scale), 32)
scale dup2 div 32 mul
dup1
swap2
mstore
mstore
// jumpi(l4, lt(i, calldatasize))
dup1 calldatasize gt l4 jumpi
pop

///////////////////////////////////////////////////
// Fifth pass (buckets): sort buckets
///////////////////////////////////////////////////
// Max group size: 7

i := 0x00
l5:
jumpi(done, eq(i, 0xf20))
jumpi(l5, lt(temp1, 64))
jumpi(sort2, eq(temp1, 64))
jumpi(sort3, eq(temp1, 96))
jumpi(sort4, eq(temp1, 128))
jumpi(sort5, eq(temp1, 160))
jumpi(sort6, eq(temp1, 192))
jumpi(sort7, eq(temp1, 224))
jumpi(sort8, eq(temp1, 256))
jump(l5)

///////////////////////////////////////////////////
// Done!
///////////////////////////////////////////////////

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

///////////////////////////////////////////////////
// Sorting networks
///////////////////////////////////////////////////

sort2: {
jumpi(end, gt(b, a))
end:
}
jump(l5)

sort3: {
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:
}
jump(l5)

sort4: // [[1 2][3 4][1 3][2 4][2 3]]
dup1 dup3 lt skip_4_1 jumpi swap1 skip_4_1:
dup3 dup5 lt skip_4_2 jumpi swap2 swap3 swap2 skip_4_2:
dup1 dup4 lt skip_4_3 jumpi swap2 skip_4_3:
dup2 dup5 lt skip_4_4 jumpi swap1 swap3 swap1 skip_4_4:
dup2 dup4 lt skip_4_5 jumpi swap1 swap2 swap1 skip_4_5:
jump(l5)

sort5: // [[1 2][3 4][1 3][2 5][1 2][3 4][2 3][4 5][3 4]]
dup1 dup3 lt skip_5_1 jumpi swap1 skip_5_1:
dup3 dup5 lt skip_5_2 jumpi swap2 swap3 swap2 skip_5_2:
dup1 dup4 lt skip_5_3 jumpi swap2 skip_5_3:
dup2 dup6 lt skip_5_4 jumpi swap1 swap4 swap1 skip_5_4:
dup1 dup3 lt skip_5_5 jumpi swap1 skip_5_5:
dup3 dup5 lt skip_5_6 jumpi swap2 swap3 swap2 skip_5_6:
dup2 dup4 lt skip_5_7 jumpi swap1 swap2 swap1 skip_5_7:
dup4 dup6 lt skip_5_8 jumpi swap3 swap4 swap3 skip_5_8:
dup3 dup5 lt skip_5_9 jumpi swap2 swap3 swap2 skip_5_9:
jump(l5)

sort6: // [[1 2][3 4][5 6][1 3][2 5][4 6][1 2][3 4][5 6][2 3][4 5][3 4]]
dup1 dup3 lt skip_6_1 jumpi swap1 skip_6_1:
dup3 dup5 lt skip_6_2 jumpi swap2 swap3 swap2 skip_6_2:
dup5 dup7 lt skip_6_3 jumpi swap4 swap5 swap4 skip_6_3:
dup1 dup4 lt skip_6_4 jumpi swap2 skip_6_4:
dup2 dup6 lt skip_6_5 jumpi swap1 swap4 swap1 skip_6_5:
dup4 dup7 lt skip_6_6 jumpi swap3 swap5 swap3 skip_6_6:
dup1 dup3 lt skip_6_7 jumpi swap1 skip_6_7:
dup3 dup5 lt skip_6_8 jumpi swap2 swap3 swap2 skip_6_8:
dup5 dup7 lt skip_6_9 jumpi swap4 swap5 swap4 skip_6_9:
dup2 dup4 lt skip_6_10 jumpi swap1 swap2 swap1 skip_6_10:
dup4 dup6 lt skip_6_11 jumpi swap3 swap4 swap3 skip_6_11:
dup3 dup5 lt skip_6_12 jumpi swap2 swap3 swap2 skip_6_12:
jump(l5)

sort7: // [[1 2][0 2][0 1][3 4][5 6][3 5][4 6][4 5][0 4][0 3][1 5][2 6][2 5][1 3][2 4][2 3]]
dup2 dup4 lt skip_7_1 jumpi swap1 swap2 swap1 skip_7_1:
dup1 dup4 lt skip_7_2 jumpi swap2 skip_7_2:
dup1 dup3 lt skip_7_3 jumpi swap1 skip_7_3:
dup4 dup6 lt skip_7_4 jumpi swap3 swap4 swap3 skip_7_4:
dup6 dup8 lt skip_7_5 jumpi swap5 swap6 swap5 skip_7_5:
dup4 dup7 lt skip_7_6 jumpi swap3 swap5 swap3 skip_7_6:
dup5 dup8 lt skip_7_7 jumpi swap4 swap6 swap4 skip_7_7:
dup5 dup7 lt skip_7_8 jumpi swap4 swap5 swap4 skip_7_8:
dup1 dup6 lt skip_7_9 jumpi swap4 skip_7_9:
dup1 dup5 lt skip_7_10 jumpi swap3 skip_7_10:
dup2 dup7 lt skip_7_11 jumpi swap1 swap5 swap1 skip_7_11:
dup3 dup8 lt skip_7_12 jumpi swap2 swap6 swap2 skip_7_12:
dup3 dup7 lt skip_7_13 jumpi swap2 swap5 swap2 skip_7_13:
dup2 dup5 lt skip_7_14 jumpi swap1 swap3 swap1 skip_7_14:
dup3 dup6 lt skip_7_15 jumpi swap2 swap4 swap2 skip_7_15:
dup3 dup5 lt skip_7_16 jumpi swap2 swap3 swap2 skip_7_16:
jump(l5)

sort8:
dup1 dup3 lt skip_8_1 jumpi swap1 skip_8_1:
dup3 dup5 lt skip_8_2 jumpi swap2 swap3 swap2 skip_8_2:
dup1 dup4 lt skip_8_3 jumpi swap2 skip_8_3:
dup2 dup5 lt skip_8_4 jumpi swap1 swap3 swap1 skip_8_4:
dup2 dup4 lt skip_8_5 jumpi swap1 swap2 swap1 skip_8_5:
dup5 dup7 lt skip_8_6 jumpi swap4 swap5 swap4 skip_8_6:
dup7 dup9 lt skip_8_7 jumpi swap6 swap7 swap6 skip_8_7:
dup5 dup8 lt skip_8_8 jumpi swap4 swap6 swap4 skip_8_8:
dup6 dup9 lt skip_8_9 jumpi swap5 swap7 swap5 skip_8_9:
dup6 dup8 lt skip_8_10 jumpi swap5 swap6 swap5 skip_8_10:
dup1 dup6 lt skip_8_11 jumpi swap4 skip_8_11:
dup2 dup7 lt skip_8_12 jumpi swap1 swap5 swap1 skip_8_12:
dup2 dup6 lt skip_8_13 jumpi swap1 swap4 swap1 skip_8_13:
dup3 dup8 lt skip_8_14 jumpi swap2 swap6 swap2 skip_8_14:
dup4 dup9 lt skip_8_15 jumpi swap3 swap7 swap3 skip_8_15:
dup4 dup8 lt skip_8_16 jumpi swap3 swap6 swap3 skip_8_16:
dup3 dup6 lt skip_8_17 jumpi swap2 swap4 swap2 skip_8_17:
dup4 dup7 lt skip_8_18 jumpi swap3 swap5 swap3 skip_8_18:
dup4 dup6 lt skip_8_19 jumpi swap3 swap4 swap3 skip_8_19:
jump(l5)

///////////////////////////////////////////////////
// Special cases
///////////////////////////////////////////////////

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

///////////////////////////////////////////////////
// BOOM!
///////////////////////////////////////////////////
explode:
selfdestruct(0)

///////////////////////////////////////////////////
// Reference implementation
///////////////////////////////////////////////////

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

``````