# Submission 077ff632...

Challenge Integer sorting hyszeth.eth 2018-37-30 653513
``````/**
* 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 {

event RemoveBeforeSubmission(uint i);

/**
* @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, input[0], input[input.length - 1]);
return input;
}

function quickSort(
uint[] input,
uint lo,
uint hi,
uint loElem,
uint hiElem
)
internal
pure
{
// Pivot (Median of 3)
uint i = uint((hi+lo)/2); // pivot index
uint pivot = input[i];
if(loElem >= pivot) { // [pivot, loElem] [hiElem]
if(loElem <= hiElem) {
// [pivot, loElem, hiElem]
// Only swap pivot and loElem
input[lo] = pivot;
input[i] = loElem;
(loElem, pivot) = (pivot, loElem);
} else {
// [pivot, hiElem, loElem] or [hiElem, pivot, loElem]
if(hiElem >= pivot) {
// [pivot, hiElem, loElem]
input[lo] = pivot;
input[i] = hiElem;
input[hi] = loElem;
(loElem, pivot, hiElem) = (pivot, hiElem, loElem);
} else {
// [hiElem, pivot, loElem]
input[lo] = hiElem;
input[hi] = loElem;
(loElem, hiElem) = (hiElem, loElem);
}
}
} else {// if(loElem < pivot) { // [loElem, pivot] [hiElem]
if(pivot >= hiElem) {
// [loElem, hiElem, pivot] or [hiElem, loElem, pivot]
if(hiElem >= loElem) {
// [loElem, hiElem, pivot]
input[i] = hiElem;
input[hi] = pivot;
(pivot, hiElem) = (hiElem, pivot);
} else {
// [hiElem, loElem, pivot]
input[lo] = hiElem;
input[i] =  loElem;
input[hi] = pivot;
(loElem, pivot, hiElem) = (hiElem, loElem, pivot);
}
} else {
// [loElem, pivot, hiElem]
// Do nothing
}
}

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

if(i >= j) {
// Sort
if(j - lo <= 7) insertionSort(input, lo, j);
else            quickSort(input, lo, j, loElem, jElem);

if(hi - i <= 7) return insertionSort(input, i, hi);
return  quickSort(input, i, hi, iElem, hiElem);
}
input[uint(i)] = jElem;
input[uint(j)] = iElem;
}
}

function insertionSort(uint[] input, uint lo, uint hi)
private
pure
{
// Base case
if(lo == hi++) return;

// If within threshold, run insertion sort instead.

uint a = input[lo];
uint i = lo + 1;
// 1
uint b = input[i];
if(a > b) {
(a, b) = (b, a);
}
if(++i == hi) {
input[lo++] = a;
input[lo++] = b;
return;
}

// 2
uint c = input[i];
if(b > c) {
(b, c) = (c, b);
if(a > b) {
(a, b) = (b, a);
}
}
if(++i == hi) {
input[lo++] = a;
input[lo++] = b;
input[lo++] = c;
return;
}

// 3
uint d = input[i];
if(c > d) {
(c, d) = (d, c);
if(b > c) {
(b, c) = (c, b);
if(a > b) {
(a, b) = (b, a);
}
}
}
if(++i == hi) {
input[lo++] = a;
input[lo++] = b;
input[lo++] = c;
input[lo++] = d;
return;
}

// 4
uint e = input[i];
if(d > e) {
(d, e) = (e, d);
if(c > d) {
(c, d) = (d, c);
if(b > c) {
(b, c) = (c, b);
if(a > b) {
(a, b) = (b, a);
}
}
}
}
if(++i == hi) {
input[lo++] = a;
input[lo++] = b;
input[lo++] = c;
input[lo++] = d;
input[lo++] = e;
return;
}

// 5
uint f = input[i];
if(e > f) {
(e, f) = (f, e);
if(d > e) {
(d, e) = (e, d);
if(c > d) {
(c, d) = (d, c);
if(b > c) {
(b, c) = (c, b);
if(a > b) {
(a, b) = (b, a);
}
}
}
}
}
if(++i == hi) {
input[lo++] = a;
input[lo++] = b;
input[lo++] = c;
input[lo++] = d;
input[lo++] = e;
input[lo++] = f;
return;
}

// 6
uint g = input[i];
if(f > g) {
(f, g) = (g, f);
if(e > f) {
(e, f) = (f, e);
if(d > e) {
(d, e) = (e, d);
if(c > d) {
(c, d) = (d, c);
if(b > c) {
(b, c) = (c, b);
if(a > b) {
(a, b) = (b, a);
}
}
}
}
}
}
if(++i == hi) {
input[lo++] = a;
input[lo++] = b;
input[lo++] = c;
input[lo++] = d;
input[lo++] = e;
input[lo++] = f;
input[lo++] = g;
return;
}

// 7
uint h = input[i];
if(g > h) {
(g, h) = (h, g);
if(f > g) {
(f, g) = (g, f);
if(e > f) {
(e, f) = (f, e);
if(d > e) {
(d, e) = (e, d);
if(c > d) {
(c, d) = (d, c);
if(b > c) {
(b, c) = (c, b);
if(a > b) {
(a, b) = (b, a);
}
}
}
}
}
}
}
if(++i == hi) {
input[lo++] = a;
input[lo++] = b;
input[lo++] = c;
input[lo++] = d;
input[lo++] = e;
input[lo++] = f;
input[lo++] = g;
input[lo++] = h;
return;
}
}
}

``````