Submission c745b7ba...
contract Sort {
function sort(uint[] /* input */) public pure returns(uint[]) {
assembly {
let tmp := 0
let a := 0
let b := 0
let done := 0
// @TODO: Mulitply by 32 soon!
let length := calldataload(36)
let output := mload(0x40)
// Trivial case; 0 or 1 elements; already sorted
if lt(length, 2) {
calldatacopy(output, 4, sub(calldatasize, 4))
return(output, mul(32, add(length, 2)))
}
// Store the dynlink0 and length for the output
mstore(output, 32)
mstore(add(output, 32), length)
let input := add(output, 64)
// tmp => value
// a => lastValue
// b => count of out-of-order elements
let io := 68
let eo := add(io, mul(32, length))
for {} lt(io, eo) {} {
tmp := calldataload(io)
b := add(b, gt(a, tmp))
a := tmp
// @TODO: May be able to make inpur or io an offset of the other?
mstore(input, tmp)
io := add(io, 32)
input := add(input, 32)
}
// No elements out-of-order; already sorted
if iszero(b) {
return(output, mul(32, add(length, 2)))
}
input := add(output, 64)
// QuickSort
// See: https://www.geeksforgeeks.org/iterative-quick-sort/
// More than 8 elements out of order; quicksort-ish
//if (tmp + 8 < length):
if gt(b, 8) {
/// Quicksort
let loo := input
let hio := add(input, mul(32, sub(length, 1)))
let stackTop := add(output, mul(32, add(length, 5))) //mload(0x40) @todo: Use 2 not 4?
let stackBase := stackTop
done := 1
for {} done {} {
// Choose a pivot
tmp := mload(and(div(add(loo, hio), 2), 0xffffffffe0))
/// Partition
io := sub(loo, 32)
let jo := add(hio, 32)
//done := 1
for {} done {} {
// Not done
done := 1
for {} done {} {
io := add(io, 32)
a := mload(io)
done := lt(a, tmp)
}
// Not done
done := 1
for {} done {} {
jo := sub(jo, 32)
b := mload(jo)
done := gt(b, tmp)
}
if lt(io, jo) {
mstore(io, b)
mstore(jo, a)
done := 1
}
}
//done := 0
/// Pick new lo and hi
//if (j > lo):
//let cond := gt(jo, loo)
//if (j > lo + 8):
let cond := gt(jo, add(loo, 256))
if cond {
//if (j + 1 < hi):
//if (j + 1 + 8 < hi):
//if lt(add(jo, 32), hio)
if lt(add(jo, 288), hio) {
mstore(stackTop, add(jo, 32))
stackTop := add(stackTop, 32)
mstore(stackTop, hio)
stackTop := add(stackTop, 32)
}
hio := jo
done := 1
}
if iszero(cond) {
// else if (j + 1 < hi):
// else if (j + 1 + 8 < hi):
//cond := lt(add(jo, 32), hio)
cond := lt(add(jo, 288), hio)
if cond {
loo := add(jo, 32)
done := 1
}
if iszero(cond) {
// else if (stackTop != 0):
//cond := eq(stackTop, stackBase)
//if iszero(cond) {
if gt(stackTop, stackBase) {
stackTop := sub(stackTop, 32)
hio := mload(stackTop)
stackTop := sub(stackTop, 32)
loo := mload(stackTop)
done := 1
}
}
}
}
}
// Linear Insertion Sort
// See: https://en.wikipedia.org/wiki/Insertion_sort
//let inputBase := add(input, 32)
// for (var i = 0; i < length; i++):
io := add(input, 32)
let ie := add(input, mul(32, length))
for {} lt(io, ie) {} {
// tmp = input[i]
// j = i
tmp := mload(io)
let jo := io
// while (j != 0):
done := 0
for { } iszero(done) { } {
if eq(jo, input) { done := 1 }
if iszero(done) {
// tmp2 = input[j - 1]
let tmp2 := mload(sub(jo, 32))
// if (tmp2 > tmp): input[j--] = tmp2
done := 1
if gt(tmp2, tmp) {
mstore(jo, tmp2)
jo := sub(jo, 32)
done := 0
}
}
}
// input[j] = tmp
mstore(jo, tmp)
io := add(io, 32)
}
return(output, mul(32, add(length, 2)))
}
}
}