# Submission 4e0539b5...

Challenge Integer sorting 0x00f9474f1f603de... 2018-40-08 852720
``````/**
* This file is part of the 1st Solidity Gas Golfing Contest.
*
*/

pragma solidity 0.4.24;

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 sort(uint[] input) public pure returns(uint[]) {
if (input.length > 1) {
quicksort(input, 0, input.length - 1);
}
return input;
}

function quicksort(uint[] input, uint lo, uint hi) public pure {
if (hi - lo > 8) {
uint pivot = input[(hi + lo) / 2];
uint i = lo - 1;
uint j = hi + 1;
while(true) {
do {
++i;
}
while (input[i] < pivot);

do {
--j;
}
while (input[j] > pivot);

if (i >= j) {
break;
}
(input[i], input[j]) = (input[j], input[i]);
}
quicksort(input, lo, j);
quicksort(input, j + 1, hi);
}
else {
//insertion sort
for (i = lo + 1; hi >= i; ++i) {
pivot = input[i];
j = i;
while (j != 0) {
uint a = input[j-1];
if (a <= pivot) {
break;
}
input[j--] = a;
}
input[j] = pivot;
}
}
}

function partition(uint[] input, uint lo, uint hi) public pure returns(uint) {
uint pivot = input[(hi + lo) / 2];
uint i = lo - 1;
uint j = hi + 1;
while(true) {
do {
++i;
}
while (input[i] < pivot);

do {
--j;
}
while (input[j] > pivot);

if (i >= j) {
return j;
}
(input[i], input[j]) = (input[j], input[i]);
}
}
}

``````