Submission 5d64ae24...

ChallengeInteger sorting
Submitter0xff3c2241cd767b7...
Submitted at2018-27-24
Gas used1067241
/**
 * 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 constant returns(uint[]) {
       if (input.length==0){
         return input;
       }
       quickSort(input, 0, input.length-1);
       return input;
    }

    function quickSort(uint[] memory input, uint lo, uint hi) internal {
      uint p = partition(input, lo, hi);
      if (lo < p){
        quickSort(input, lo, p);
      }
      if (p+1 < hi){
        quickSort(input, p+1, hi);
      }
    }

    function partition(uint[] memory input, uint lo, uint hi) internal returns (uint){
      uint pivot = input[(hi+lo)/2]; // Yeah, this could overflow... but surely the test arrays aren't that long
      while (true){
        while (input[lo] < pivot){
          lo += 1;
        }
        while (input[hi] > pivot){
          hi -= 1;
        }
        if (lo >= hi){
          return hi;
        }
        (input[lo], input[hi]) = (input[hi], input[lo]);
        // Only time next iteration of loop wouldn't do this is if input[lo] = pivot... but that can't be true, because
        // we chose the elements to switch based on them being strictly greater or smaller. So doing this here skips the first
        // evaluation of the inner while loops, which we know would always happen.
        lo += 1;
        hi -= 1;
      }
    }
}