# Submission b7e39ae5...

Challenge Integer sorting wicketh.eth 2018-41-12 707270
pragma solidity 0.4.24;

contract Sort {

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

uint256 constant RADIX = 80;

function sort(uint[] input)
external payable returns(uint[])
{
uint256 l = input.length;
if (l < 2) return input;

uint256[] memory output = new uint256[](input.length);

// First pass: find upper bound to values and compute scaling factor
uint256 scale = RADIX;
for(uint256 i = 0; i < input.length; i++) {
scale |= input[i];
}
scale = (scale + RADIX - 1) / RADIX;

// Second pass: count buckets
for(i = 0; i < input.length; i++) {
counts[input[i] / scale]++;
}
uint256 acc = counts[0];
for(i = 1; i < RADIX; i++) {
acc = counts[i] += acc;
}

// Third pass: move to buckets
for(i = 0; i < input.length; i++) {
uint256 val = input[i];
output[--counts[val / scale]] = val;
}

// Fourth pass: sort buckets
acc = counts[0];
for(i = 1; i < RADIX - 1; i++) {
val = counts[i];
if (acc < val - 1) {
sort(output, acc, val - 1);
}
acc = val;
}
if (acc < output.length - 1) {
sort(output, acc, output.length - 1);
}

return output;
}

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) {
iv = input[++i];
}
while (jv > pivot) {
jv = input[--j];
}
if (i >= j) {
i = j + 1;
break;
}
input[i++] = jv;
input[j--] = iv;
}

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