# Submission 5d781625...

Challenge Integer sorting wicketh.eth 2018-49-12 707249
``````pragma solidity 0.4.24;

contract Sort {

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

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

uint256[] memory output = new uint256[](l);

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

// Second pass: count buckets
for(i = 0; i < l; 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 < l; 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 < l - 1) {
sort(output, acc, l - 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);
}
}

``````