# Submission 309f059c...

Challenge Integer sorting hyszeth.eth 2018-38-24 731951
``````/**
* 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
{
uint iElem;
uint jElem;
if(hi - lo > 7) {
// Pivot (Median of 3)
i = uint((hi+lo)/2); // pivot index
iElem = input[lo];
uint pivot = input[i];
jElem = input[hi];
// [iElem, pivot, jElem]
if(iElem >= pivot) { // [pivot, iElem] [jElem]
if(iElem <= jElem) {
// [pivot, iElem, jElem]
// Only swap pivot and iElem
input[lo] = pivot;
input[i] = iElem;
pivot = iElem;
} else {
// [pivot, jElem, iElem] or [jElem, pivot, iElem]
if(jElem >= pivot) {
// [pivot, jElem, iElem]
input[lo] = pivot;
input[i] = jElem;
input[hi] = iElem;
pivot = jElem;
} else {
// [jElem, pivot, iElem]
input[lo] = jElem;
input[hi] = iElem;
}
}
} else {// if(iElem < pivot) { // [iElem, pivot] [jElem]
if(pivot >= jElem) {
// [iElem, jElem, pivot] or [jElem, iElem, pivot]
if(jElem >= iElem) {
// [iElem, jElem, pivot]
input[i] = jElem;
input[hi] = pivot;
pivot = jElem;
} else {
// [jElem, iElem, pivot]
input[lo] = jElem;
input[i] =  iElem;
input[hi] = pivot;
pivot = iElem;
}
} else {
// [iElem, pivot, jElem]
// Do nothing
}
}

// Hoare pivot algorithm
// Note we skip the lo/hi elements because
// we already know they're in the correct position.
uint i = lo;
uint j = hi;
while(true) {
while((iElem=input[uint(++i)]) <= pivot) {}
while((jElem=input[uint(--j)]) >= pivot) {}

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

// Sort
quickSort(input, lo, j);
quickSort(input, i, hi);
return;
}

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

``````