Submission 3f76ab0e...
/**
* This file is part of the 1st Solidity Gas Golfing Contest.
*
* This work is licensed under Creative Commons Attribution ShareAlike 3.0.
* https://creativecommons.org/licenses/by-sa/3.0/
*/
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[]) {
if (input.length < 2) {
return input;
}
uint t = input.length - 1;
sortFew(input, 0, t);
if (t < 3) {
return input;
}
quickSortAsc(input, 0, t, input[t / 2]);
return input;
}
function sortFew(uint [] input, uint head, uint tail) internal pure
{
if (tail - head == 1) {
if (input[head] > input[tail]) {
(input[head], input[tail]) = (input[tail], input[head]);
}
} else {
uint tmp = (head + tail) / 2;
if (input[head] < input[tmp]) {
if (input[tmp] < input[tail]) {
} else {
if (input[head] < input[tail]) {
(input[tmp], input[tail]) = (input[tail], input[tmp]);
} else {
(input[head], input[tmp], input[tail]) = (input[tail], input[head], input[tmp]);
}
}
} else {
if (input[tmp] < input[tail]) {
if (input[head] < input[tail]) {
(input[head], input[tmp]) = (input[tmp], input[head]);
} else {
(input[head], input[tmp], input[tail]) = (input[tmp], input[tail], input[head]);
}
} else {
(input[head], input[tail]) = (input[tail], input[head]);
}
}
}
}
function insertSortAsc(uint[] memory input, uint head, uint tail) internal pure {
for (uint i = head+1; i <= tail; i++) {
uint tmp = input[i];
uint j;
for (j = i-1; j >= head; j--) {
if (tmp > input[j]) {
break;
} else {
input[j+1] = input[j];
}
}
input[j+1] = tmp;
}
}
function quickSortAsc(uint[] memory input, uint head, uint tail, uint mval) internal pure
{
if (tail - head < 3) {
sortFew(input, head, tail);
return;
}
if (tail - head <= 8 && head != 0) {
insertSortAsc(input, head, tail);
return;
}
uint h = head;
uint t = tail;
while (h <= t) {
while (input[h] < mval) {
h++;
}
while (mval < input[t]) {
t--;
}
if (h <= t) {
(input[h], input[t]) = (input[t], input[h]);
h++;
if (t > 0) {
t--;
}
}
}
if (head < t) {
quickSortAsc(input, head, t, input[(head + t) / 2]);
}
if (h < tail) {
quickSortAsc(input, h, tail, input[(h + tail) / 2]);
}
}
}