Challenge Integer sorting sggc.yuetloo.eth 2018-16-29 867837
``````/**
* This is a modified version of the original contract from
*   https://github.com/arachnid/sggc.git
*
* This file is part of the 1st Solidity Gas Golfing Contest.
*
*/
pragma solidity ^0.4.21;

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 ) {
qsort(input, 0, int(input.length)-1);
}
}
return input;
}

function alreadySorted(uint[] input) internal pure returns(bool) {

bool ascending = (input[1] >= input[0]);
for( uint i = 1; i < input.length; i++ ) {
if( ascending )
{
if( input[i-1] > input[i] ) return false;
} else
{
if( input[i-1] < input[i] ) return false;
}
}

if( !ascending )
{
uint j = 0;
for( i = 0; i < uint(input.length/2); i++ )
{
j = input.length-i-1;
(input[i], input[j]) = (input[j], input[i]);
}
}

return true;
}

function qsort(uint[] input, int lo, int hi) internal pure {
if(lo < hi) {
if( (hi - lo) < 5 ) {
insertionSort(input, uint(lo), uint(hi+1));
} else {
int p = partition(input, lo, hi);
qsort(input, lo, p);
qsort(input, p + 1, hi);
}
}
}

function partition(uint[] input, int lo, int hi) internal pure returns(int) {
uint pivot = input[uint(lo+((hi-lo)/2))];
int i = lo - 1;
int j = hi + 1;
while( true ) {
do { i++; } while( input[uint(i)] < pivot );
do { j--; } while( input[uint(j)] > pivot );
if( i >= j ) return j;
(input[uint(i)], input[uint(j)]) = (input[uint(j)], input[uint(i)]);
}
}

function insertionSort(uint[] input, uint lo, uint hi) internal pure {
for( uint i = lo+1; i < hi; i++ )
{
uint j = i;
while(j > 0 && input[uint(j-1)] > input[uint(j)]) {
(input[(j-1)], input[j]) = (input[j], input[(j-1)]);
j--;
}
}
}

}

``````