Submission 782442d0...

Challenge Integer sorting 0xd0b40847c318da4... 2018-12-10 1343820
``````/**
* 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 < 5) {
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 partition(uint[] a, uint lo, uint hi) internal pure returns (uint) {
uint256 mid = (lo + hi) / 2;
if (a[mid] < a[hi])
(a[mid], a[hi]) = (a[hi], a[mid]);
if (a[lo] < a[hi])
(a[lo], a[hi]) = (a[hi], a[lo]);
if (a[mid] < a[lo])
(a[lo], a[mid]) = (a[mid], a[lo]);

uint pivot = a[lo];
uint i = lo+1;
uint j = 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]);
}
}
}

``````