# Submission 96e4ac8e...

Challenge Integer sorting hyszeth.eth 2018-38-17 812648
``````/**
* This file is part of the 1st Solidity Gas Golfing Contest.
*
*
* Author: Greg Hysen (@hysz)
* Date: June, 2018
*/

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 == 0) return input;
quickSort(input, 0, input.length - 1);
return input;
}

function quickSort(
uint[] input,
uint lo,
uint hi
)
internal
pure
{
// Pivot (Median of 3)
i = uint((hi+lo)/2); // pivot index
uint pivot = input[i];
if((iElem=input[lo]) > pivot) {
(input[lo], input[i]) = (pivot, iElem);
pivot = iElem;
}
if((iElem=input[lo]) > (jElem=input[hi])) (input[lo], input[hi]) = (jElem, iElem);
if((iElem=input[i]) > (jElem=input[hi])) {
(input[i], input[hi]) = (jElem, iElem);
pivot = jElem;
}

// Hoare pivot algorithm
uint i = lo - 1;
uint j = hi + 1;
uint iElem;
uint jElem;
while(true) {
while((iElem=input[uint(++i)]) < pivot) {}
while((jElem=input[uint(--j)]) > pivot) {}

if(i >= j) break;
(input[uint(i)], input[uint(j)]) = (jElem, iElem);
}

// Sort
i = j - lo;
if(i > 11) quickSort(input, lo, j);
else if(i > 1) insertionSort(input, lo, j);

i = hi - ++j;
if(i > 11) quickSort(input, j, hi);
else if(i > 1) insertionSort(input, j, hi);
}

function insertionSort(
uint[] input,
uint lo,
uint hi
)
internal
pure
{
// If within threshold, run insertion sort instead.
uint i = lo + 1;
while(i <= hi) {
uint j = i;
uint jElem=input[j];
uint iElem;
while(j > lo && (iElem=input[j-1]) > jElem) {
input[j--] = iElem;
}
if(j != i++) input[j] = jElem;
}
}
}

``````