# Submission c745b7ba...

Challenge Integer sorting ricmoo.firefly.eth 2018-06-29 529510
``````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!

// Trivial case; 0 or 1 elements; already sorted
if lt(length, 2) {
calldatacopy(output, 4, sub(calldatasize, 4))
}

// Store the dynlink0 and length for the output
mstore(output, 32)

// 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) {} {
a := tmp
// @TODO: May be able to make inpur or io an offset of the other?
mstore(input, tmp)
}

// No elements out-of-order; already sorted
if iszero(b) {
}

// 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 stackBase := stackTop

done := 1
for {} done {} {

// Choose a pivot

/// Partition

io := sub(loo, 32)
//done := 1
for {} done {} {

// Not done
done := 1
for {} done {} {
done := lt(a, tmp)
}

// Not done
done := 1
for {} done {} {
jo := sub(jo, 32)
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):
mstore(stackTop, hio)
}
hio := jo
done := 1
}

if iszero(cond) {

// else if (j + 1 < hi):
// else if (j + 1 + 8  < hi):
if cond {
done := 1
}

if iszero(cond) {

// else if (stackTop != 0):
//cond := eq(stackTop, stackBase)
//if iszero(cond) {
if gt(stackTop, stackBase) {
stackTop := sub(stackTop, 32)
stackTop := sub(stackTop, 32)
done := 1
}
}
}
}
}

// Linear Insertion Sort
// See: https://en.wikipedia.org/wiki/Insertion_sort

// for (var i = 0; i < length; i++):
let ie := add(input, mul(32, length))
for {} lt(io, ie) {} {

// tmp = input[i]
// j = i
let jo := io

// while (j != 0):
done := 0
for { } iszero(done) { } {
if eq(jo, input) { done := 1 }
if iszero(done) {
// tmp2 = input[j - 1]

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