# Submission f99f6a29...

Challenge Integer sorting zac.creditmint.eth 2018-52-27 459469
``````/**
* This file is part of the 1st Solidity Gas Golfing Contest.
*
*/

pragma solidity ^0.4.23;

contract Sort {
/**
* @dev Sorts a list of integers in ascending order.
*
* The input list may be of any length.
*
* @param input The list of integers to sort.
* @return The sorted list.
*/
function insertionNonsense(uint[] input) external view returns(uint[]) {
assembly {
let size := sub(calldatasize, 0x44)
mstore(0x40, sort_two)
mstore(0x60, sort_three)
mstore(0x80, sort_four)
mstore(0xa0, sort_five)
mstore(0xc0, sort_six)
mstore(0xe0, sort_seven)
mstore(0x100, sort_eight)
calldatacopy(0x120, 0x04, calldatasize)
0x160
pop
finished_insertion_sort:
sort_two:
dup2 dup2 lt        // 0 1 p
two_0_1_skip jumpi
swap1
two_0_1_skip:               // (max) (min) p
dup3 mstore
jump(finished_insertion_sort)

sort_three:
dup2 0x20 add       // p1 p2 p
dup2 mload          // 2 p1 p2 p
dup2 mload          // 1 2 p1 p2 p
dup5 mload          // 0 1 2 p1 p2 p

dup3 dup3 lt three_1_2_skip jumpi
swap2               // 2 1 0
swap1               // 1 2 0
swap2               // 0 2 1
three_1_2_skip:         // 0 1 2
dup3 dup2 lt three_0_2_skip jumpi
swap2
three_0_2_skip:         // 0 1 2
dup2 dup2 lt three_0_1_skip jumpi
swap1
three_0_1_skip:         // 0 1 2 p1 p2 p
dup6 mstore             // 1 2 p1 p2 p
swap3 mstore            // p1 1 p
mstore                  // p

jump(finished_insertion_sort)

sort_four:
dup3 mload          // 3 p1 p2 p3 p
dup3 mload          // 1 2 3 p1 p2 p3 p
dup7 mload          // 0 1 2 3 p1 p2 p3

dup2 dup2 lt four_0_1_skip jumpi
swap1
four_0_1_skip:          // 0 1 2 3 p
dup4 dup4 lt four_2_3_skip jumpi
swap3                   // 3 1 2 0
swap2                   // 2 1 3 0
swap3                   // 0 1 3 2
four_2_3_skip:          // 0 1 2 3 p
dup3 dup2 lt four_0_2_skip jumpi
swap2
four_0_2_skip:          // 0 1 2 3 p
dup4 dup3 lt four_1_3_skip jumpi
swap3 swap1 swap3
four_1_3_skip:          // 0 1 2 3 p
dup3 dup3 lt four_1_2_skip jumpi
swap1 swap2 swap1
four_1_2_skip:          // 0 1 2 3 p1 p2 p3 p
dup8 mstore             // 1 2 3 p1 p2 p3 p
swap4 mstore            // 3 p1 1 p3 p
swap2 mstore
swap1 mstore

jump(finished_insertion_sort)

sort_five:
dup4 0x20 add       // p1 p2 p3 p4 p
dup4 mload          // 4 p1 p2 p3 p4 p
dup9 mload          // 0 1 2 3 4 p1 p2 p3 p4 p
dup2 dup2 lt five_0_1_skip jumpi
swap1
five_0_1_skip:          // 0 1 2 3 4
dup5 dup5 lt five_3_4_skip jumpi
swap3 swap4 swap3
five_3_4_skip:          // 0 1 2 3 4
dup5 dup4 lt five_2_4_skip jumpi
swap2 swap4 swap2
five_2_4_skip:          // 0 1 2 3 4
dup4 dup4 lt five_2_3_skip jumpi
swap2 swap3 swap2
five_2_3_skip:          // 0 1 2 3 4
dup5 dup3 lt five_1_4_skip jumpi
swap1 swap4 swap1
five_1_4_skip:          // 0 1 2 3 4
dup4 dup2 lt five_0_3_skip jumpi
swap3
five_0_3_skip:          // 0 1 2 3 4
dup3 dup2 lt five_0_2_skip jumpi
swap2
five_0_2_skip:
dup4 dup3 lt five_1_3_skip jumpi
swap1 swap3 swap1
five_1_3_skip:          // 0 1 2 3 4
dup3 dup3 lt five_1_2_skip jumpi
swap1 swap2 swap1
five_1_2_skip:          // 0 1 2 3 4 p1 p2 p3 p4 p
dup10 mstore            // 1 2 3 4 p1 p2 p3 p4 p
swap5 mstore            // 3 4 p1 1 p3 p4 p
swap5 mstore            // p1 1 p3 3 p
mstore                  // p3 3 p
mstore                  // p
jump(finished_insertion_sort)

sort_six:
dup5 0x20 add       // p1 p2 p3 p4 p
dup5 mload          // 4 p1 p2 p3 p4 p
dup11 mload          // 0 1 2 3 4 5 p1 p2 p3 p4 p5 p

dup3 dup3 lt six_1_2_skip jumpi
swap1 swap2 swap1
six_1_2_skip:
dup6 dup6 lt six_4_5_skip jumpi
swap4 swap5 swap4
six_4_5_skip:
dup3 dup2 lt six_0_2_skip jumpi
swap2
six_0_2_skip:
dup6 dup5 lt six_3_5_skip jumpi
swap3 swap5 swap3
six_3_5_skip:
dup2 dup2 lt six_0_1_skip jumpi
swap1
six_0_1_skip:
dup5 dup5 lt six_3_4_skip jumpi
swap3 swap4 swap3
six_3_4_skip:
dup6 dup4 lt six_2_5_skip jumpi
swap2 swap5 swap2
six_2_5_skip:
dup4 dup2 lt six_0_3_skip jumpi
swap3
six_0_3_skip:
dup5 dup3 lt six_1_4_skip jumpi
swap1 swap4 swap1
six_1_4_skip:
dup5 dup4 lt six_2_4_skip jumpi
swap2 swap4 swap2
six_2_4_skip:
dup4 dup3 lt six_1_3_skip jumpi
swap1 swap3 swap1
six_1_3_skip:
dup4 dup4 lt six_2_3_skip jumpi
swap2 swap3 swap2
six_2_3_skip:           // 0 1 2 3 4 5 p1 p2 p3 p4 p5 p
dup12 mstore            // 1 2 3 4 5 p1 p2 p3 p4 p5 p
swap6 mstore            // 3 4 5 p1 1 p3 p4 p5 p
swap6 mstore            // 5 p1 1 p3 3 p5 p
swap2 swap1 mstore      // 5 p3 3 p5 p
swap2 swap1 mstore      // 5 p5 p
swap1 mstore
jump(finished_insertion_sort)

sort_seven:
dup6 0x20 add       // p1 p2 p3 p4 p5 p6 p
dup6 mload          // 4 p1 p2 p3 p4 p
dup13 mload          // 0 1 2 3 4 5 6 p1 p2 p3 p4 p5 p6 p

dup3 dup3 lt seven_1_2_skip jumpi
swap1 swap2 swap1
seven_1_2_skip:
dup5 dup5 lt seven_3_4_skip jumpi
swap3 swap4 swap3
seven_3_4_skip:
dup7 dup7 lt seven_5_6_skip jumpi
swap5 swap6 swap5
seven_5_6_skip:
dup3 dup2 lt seven_0_2_skip jumpi
swap2
seven_0_2_skip:
dup6 dup5 lt seven_3_5_skip jumpi
swap3 swap5 swap3
seven_3_5_skip:
dup7 dup6 lt seven_4_6_skip jumpi
swap4 swap6 swap4
seven_4_6_skip:
dup2 dup2 lt seven_0_1_skip jumpi
swap1
seven_0_1_skip:
dup6 dup6 lt seven_4_5_skip jumpi
swap4 swap5 swap4
seven_4_5_skip:
dup7 dup4 lt seven_2_6_skip jumpi
swap2 swap6 swap2
seven_2_6_skip:
dup5 dup2 lt seven_0_4_skip jumpi
swap4
seven_0_4_skip:
dup6 dup3 lt seven_1_5_skip jumpi
swap1 swap5 swap1
seven_1_5_skip:
dup4 dup2 lt seven_0_3_skip jumpi
swap3
seven_0_3_skip:
dup6 dup4 lt seven_2_5_skip jumpi
swap2 swap5 swap2
seven_2_5_skip:
dup4 dup3 lt seven_1_3_skip jumpi
swap1 swap3 swap1
seven_1_3_skip:
dup5 dup4 lt seven_2_4_skip jumpi
swap2 swap4 swap2
seven_2_4_skip:
dup4 dup4 lt seven_2_3_skip jumpi
swap2 swap3 swap2
seven_2_3_skip:         // 0 1 2 3 4 5 6 p1 p2 p3 p4 p5 p6 p
dup14 mstore            // 1 2 3 4 5 6 p1 p2 p3 p4 p5 p6 p
swap7 mstore            // 3 4 5 6 p1 1 p3 p4 p5 p6 p
swap7 mstore            // 5 6 p1 1 p3 3 p5 p6 p
swap7 mstore            // p1 1 p3 3 p5 5 p
mstore
mstore
mstore
jump(finished_insertion_sort)

sort_eight:
dup7 0x20 add       // p1 p2 p3 p4 p5 p6 p
dup7 mload          // 4 p1 p2 p3 p4 p
dup15 mload          // 0 1 2 3 4 5 6 7 p1 p2 p3 p4 p5 p6 p7 p

dup2 dup2 lt eight_0_1_skip jumpi
swap1
eight_0_1_skip:
dup4 dup4 lt eight_2_3_skip jumpi
swap2 swap3 swap2
eight_2_3_skip:
dup6 dup6 lt eight_4_5_skip jumpi
swap4 swap5 swap4
eight_4_5_skip:
dup8 dup8 lt eight_6_7_skip jumpi
swap6 swap7 swap6
eight_6_7_skip:
dup3 dup2 lt eight_0_2_skip jumpi
swap2
eight_0_2_skip:
dup4 dup3 lt eight_1_3_skip jumpi
swap1 swap3 swap1
eight_1_3_skip:
dup7 dup6 lt eight_4_6_skip jumpi
swap4 swap6 swap4
eight_4_6_skip:
dup8 dup7 lt eight_5_7_skip jumpi
swap5 swap7 swap5
eight_5_7_skip:
dup3 dup3 lt eight_1_2_skip jumpi
swap1 swap2 swap1
eight_1_2_skip:
dup7 dup7 lt eight_5_6_skip jumpi
swap5 swap6 swap4
eight_5_6_skip:
dup5 dup2 lt eight_0_4_skip jumpi
swap4
eight_0_4_skip:
dup8 dup5 lt eight_3_7_skip jumpi
swap7 swap3 swap7
eight_3_7_skip:
dup6 dup3 lt eight_1_5_skip jumpi
swap1 swap5 swap1
eight_1_5_skip:
dup7 dup4 lt eight_2_6_skip jumpi
swap2 swap6 swap2
eight_2_6_skip:
dup5 dup3 lt eight_1_4_skip jumpi
swap1 swap4 swap1
eight_1_4_skip:
dup7 dup5 lt eight_3_6_skip jumpi
swap3 swap6 swap3
eight_3_6_skip:
dup5 dup4 lt eight_2_4_skip jumpi
swap2 swap4 swap2
eight_2_4_skip:
dup6 dup5 lt eight_3_5_skip jumpi
swap3 swap5 swap3
eight_3_5_skip:
dup5 dup5 lt eight_3_4_skip jumpi
swap3 swap4 swap3
eight_3_4_skip:         // 0 1 2 3 4 5 6 7 p1 p2 p3 p4 p5 p6 p7 p
dup16 mstore            // 1 2 3 4 5 6 7 p1 p2 p3 p4 p5 p6 p7 p
swap8 mstore            // 3 4 5 6 7 p1 1 p3 p4 p5 p6 p7 p
swap8 mstore            // 5 6 7 p1 1 p3 3 p5 p6 p7 p
swap8 mstore            // 7 p1 1 p3 3 p5 5 p7 p
swap2 swap1 mstore      // 7 p3 3 p5 5 p7 p
swap2 swap1 mstore      // 7 p5 5 p7 p
swap2 swap1 mstore      // 7 p7 p
swap1 mstore
jump(finished_insertion_sort)
}
}
function sort(uint[] input) external view returns(uint[]) {
assembly {
calldatacopy(0, 0x04, calldatasize)
let it := 0x60
let size := sub(calldatasize, 0x24)
let current
check_if_perfect_start:
jumpi(check_if_perfect_start, lt(it, end))
// hey, it's perfect!
check_if_perfect_skip:
quickSort(0x40, size)
function quickSort(p_low, p_high) {
if lt(p_low, p_high) {
let pi := partition(p_low, p_high)
quickSort(p_low, sub(pi, 0x20))
}
}
function partition(p_low, p_high) -> v {
let i := sub(p_low, 0x20)
let t := 0x00
let moduli := div(sub(p_high, p_low), 0x20)
let factor := add(p_low, mul(mulmod(gas, 0x30644e72e131a029b85045b68181585d97816a916871ca8d3c208c16d87cfd47, moduli), 0x20))
mstore(p_high, pivot)
for {let j := p_low} lt(j, p_high) {j := add(j, 0x20)} {