Submission 9c7ad969...

ChallengeInteger sorting
Submittersggc.yuetloo.eth
Submitted at2018-16-29
Gas used867837
/**
 * 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.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 ) {
            if( !alreadySorted(input) ) {
              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--;
          }
       }
    }

}