# Submission 5dd22e40...

Challenge Integer sorting wicketh.eth 2018-58-31 999377
``````/**
* 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[]) {
sort(input, 0, int(input.length - 1));
return input;
}

function sort(uint[] input, int lo, int hi)
internal pure
{
if(lo < hi) {
if (hi - lo == 1) {
uint lov = input[uint(lo)];
uint hiv = input[uint(hi)];
if (lov > hiv) {
input[uint(lo)] = hiv;
input[uint(hi)] = lov;
}
} else {
int slo;
int shi;
(slo, shi) = partition(input, lo, hi);
sort(input, lo, slo);
sort(input, shi, hi);
}
}
}

function partition(uint[] input, int lo, int hi)
internal pure
returns(int, int)
{
uint pivot = input[uint((lo + hi) / 2)];
int i = lo;
int j = hi;
while (true) {
uint iv = input[uint(i)];
uint jv = input[uint(j)];
while (iv < pivot) {
i++;
iv = input[uint(i)];
}
while (jv > pivot) {
j--;
jv = input[uint(j)];
}
if (i >= j) {
return (j, j + 1);
}
input[uint(i)] = jv;
input[uint(j)] = iv;
i += 1;
j -= 1;
}
}

function insertionSort(uint[] input, int lo, int hi)
internal pure
{
int i = lo + 1;
while (i <= hi) {
uint key = input[uint(i)];
int j = i - 1;
while(j >= lo && input[uint(j)] > key) {
input[uint(j + 1)] = input[uint(j)];
j -= 1;
}
input[uint(j + 1)] = key;
i++;
}
}
}

``````