# Submission 3ce9e9bb...

Challenge Integer sorting 0xd0b40847c318da4... 2018-25-10 1482425
``````/**
* 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 <= 1) {
return input;
}
quickSort(input, 0, input.length - 1);
return input;
}

function quickSort(uint[] a, uint lo, uint hi) internal pure {
if (lo >= hi)
return;

if (hi - lo == 1) {
if (a[hi] < a[lo]) {
(a[lo], a[hi]) = (a[hi], a[lo]);
}
return;
}

if (hi - lo <= 6) {
insertionSort(a, lo, hi);
return;
}

uint p = partition(a, lo, hi);
if (p > lo) {
quickSort(a, lo, p-1);
}
if (p < hi) {
quickSort(a, p+1, hi);
}
}

function insertionSort(uint[] a, uint lo, uint hi) internal pure {
uint low;
for (uint i = lo; i < hi; i++) {
low = i;
for (uint j = i+1; j <= hi; j++) {
if (a[j] < a[low]) {
low = j;
}
}
if (low != i) {
(a[i], a[low]) = (a[low], a[i]);
}
}
}

function median(uint[] a, uint x, uint y, uint z) internal pure {
(uint X, uint Y, uint Z) = (a[x], a[y], a[z]);
if (X > Y) {
if (Y > Z) {
(a[x], a[y]) = (Y, X);
} else if (X > Z) {
(a[x], a[z]) = (Z, X);
}
} else {
if (X > Z) {
} else if (Y > Z) {
(a[x], a[z]) = (Z, X);
} else {
(a[x], a[y]) = (Y, X);
}
}
}

function partition(uint[] a, uint lo, uint hi) internal pure returns (uint) {
median(a, lo, (lo + hi) / 2, hi);

(uint pivot, uint i, uint j) = (a[lo], lo+1, hi);
while (true) {
while (i <= j && a[i] <= pivot) {
i++;
}

while (i <= j && a[j] > pivot) {
j--;
}

if (j < i) {
(a[lo], a[j]) = (a[j], a[lo]);
return j;
}

(a[i], a[j]) = (a[j], a[i]);
}
}
}

``````