# Submission 1d6b30e5...

Challenge Integer sorting 0xff3c2241cd767b7... 2018-29-25 932370
``````/**
* This file is part of the 1st Solidity Gas Golfing Contest.
*
*/

pragma solidity 0.4.24;

contract Sort {

// This implementation: 1028435
/**
* @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 constant returns(uint[]) {
if (input.length<=1){
return input;
}
quickSort(input, 0, input.length-1);
return input;
}

function quickSort(uint[] memory input, uint lo, uint hi) internal {
uint lo2 = lo;
uint hi2 = hi;
if (hi-lo>3){
uint pivot = input[(hi2+lo2)/2]; // Yeah, this could overflow... but surely the test arrays aren't that long
while (true){
while (input[lo2] < pivot){
lo2 += 1;
}
while (input[hi2] > pivot){
hi2 -= 1;
}
if (lo2 >= hi2){
break;
}
(input[lo2], input[hi2]) = (input[hi2], input[lo2]);
// Only time next iteration of loop wouldn't do this is if input[lo] = pivot... but that can't be true, because
// we chose the elements to switch based on them being strictly greater or smaller. So doing this here skips the first
// evaluation of the inner while loops, which we know would always happen.
lo2 += 1;
hi2 -= 1;
}
if (lo < hi2){
quickSort(input, lo, hi2);
}
if (hi2+1 < hi){
quickSort(input, hi2+1, hi);
}
} else {
// From wiki:
// However, insertion sort is one of the fastest algorithms for sorting very small arrays, even faster than quicksort;
// indeed, good quicksort implementations use insertion sort for arrays smaller than a certain threshold, also when arising
// as subproblems; the exact threshold must be determined experimentally and depends on the machine, but is commonly around ten.
uint i = 1;
while (i < hi-lo+1){
uint j = i;
while (j>0 && input[lo+j-1] > input[lo+j]){
(input[lo+j-1], input[lo+j]) = (input[lo+j], input[lo+j-1]);
j -=1;
}
i+=1;
}
}
}

}

``````