# Submission 0541e7d0...

Challenge Integer sorting 0xabcdef0db461f2f... 2018-18-03 1087641
``````/**
* 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[]) {
if (input.length < 2) {
return input;
}
if (input.length == 2) {
if (input[0] > input[1]) {
(input[0], input[1]) = (input[1], input[0]);
}
return input;
}
dualQuickSortAsc(input, 0, input.length-1);
return input;
}

function choosePivot(uint[] input, uint head, uint tail) internal pure returns(uint, uint) {
uint diff = (tail - head) / 3;
uint left = head + diff;
uint right = tail - diff;
if (input[head] > input[tail]) {
}
if (input[head] > input[right]) {
}
if (input[head] > input[left]) {
}
if (input[left] > input[right]) {
(input[left], input[right]) = (input[right], input[left]);
}
if (input[left] > input[tail]) {
(input[left], input[tail]) = (input[tail], input[left]);
}
if (input[right] > input[tail]) {
(input[right], input[tail]) = (input[tail], input[right]);
}
return (input[left], input[right]);
}

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 dualQuickSortAsc(uint[] memory input, uint head, uint tail) internal pure
{
if (tail - head <= 16 && head != 0) {
return;
}
uint x;
uint y;
(x, y) = choosePivot(input, head, tail);
uint h = head+1;
uint t = tail-1;
while (input[h] < x) {
h++;
}
while (input[t] > y) {
t--;
}
for (uint k = h; k <= t; ) {
if (input[k] < x) {
(input[h], input[k]) = (input[k], input[h]);
h++;
k++;
} else if (input[k] > y) {
(input[t], input[k]) = (input[k], input[t]);
t--;
} else {
k++;
}
}
if (h < t) {
dualQuickSortAsc(input, h, t);
}
h--;
t++;
if (head < h) {