Submission 9b8e9fac...

ChallengeInteger sorting
Submittersggc.yuetloo.eth
Submitted at2018-34-24
Gas used1593828
/**
 * Author: Yuet Loo Wong
 * 
 * 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.
 *
 * This work is licensed under Creative Commons Attribution ShareAlike 3.0.
 * https://creativecommons.org/licenses/by-sa/3.0/
 */

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


    function alreadySorted(uint[] input) internal pure returns(bool) {
       uint prev = input[0];
        
       bool ascending = (input[1] > input[0]);
       for( uint i = 1; i < input.length; i++ ) {
          if( ascending )
          {
             if( prev > input[i] ) return false;
          } else 
          {
             if( prev < input[i] ) return false;
          }
          prev = input[i];
       }

       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 sort(uint[] input, int lo, int hi) internal pure {
        if(lo < hi) {
            int p = partition(input, lo, hi);
            sort(input, lo, p);
            sort(input, p + 1, hi);
        }
    }

    function partition(uint[] input, int lo, int hi) internal pure returns(int) {
        uint pivot = input[uint(lo)];
        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)]);
        }
 }
}