# Submission 0e5056de...

Challenge Integer sorting wicketh.eth 2018-27-09 879035
``````pragma solidity 0.4.24;

contract Sort {

// @author Remco Bloemen <[email protected]>

function sort(uint[] input)
public payable returns(uint[])
{
uint256 l = input.length;
if (l < 2) return input;
sort(input, 0, l - 1);
return input;
}

function sort(uint[] memory input, uint256 lo, uint256 hi)
internal view
{
uint256 d = hi - lo;
if (d < 3) {
// Optimize for two values
if (d == 1) {
uint256 a = input[lo];
uint256 b = input[hi];
if (b < a) {
input[lo] = b;
input[hi] = a;
}
return;
}

// Optimize for three values
a = input[lo];
b = input[lo + 1];
uint256 c = input[hi];
if (a < b) {
if (b < c) {
return;
} else {
if (c < a) {
input[lo] = c;
input[lo + 1] = a;
input[hi] = b;
return;
} else {
input[lo + 1] = c;
input[hi] = b;
return;
}
}
} else {
if (a < c) {
input[lo] = b;
input[lo + 1] = a;
input[hi] = c;
return;
} else {
if (b < c) {
input[lo] = b;
input[lo + 1] = c;
input[hi] = a;
return;
} else {
input[lo] = c;
input[lo + 1] = b;
input[hi] = a;
return;
}
}
}
}

// partition
uint256 pivot = input[(lo + hi) / 2];
uint256 i = lo;
uint256 j = hi;
while (true) {
uint iv = input[i];
uint jv = input[j];
while (iv < pivot) {
i++;
iv = input[i];
}
while (jv > pivot) {
j--;
jv = input[j];
}
if (i >= j) {
i = j + 1;
break;
}
input[i] = jv;
input[j] = iv;
i += 1;
j -= 1;
}

// Recurse
if (lo < j) sort(input, lo, j);
if (i < hi) sort(input, i, hi);
}
}

``````