Submission 9c7cf011...

ChallengeInteger sorting
Submitter0xff3c2241cd767b7...
Submitted at2018-30-25
Gas used927422
/**
 * 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 {

    // This implementation: 1021799
    /**
     * @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<=1){
         return input;
       }
       quickSort(input, 0, input.length-1);
       return input;
    }

    function quickSort(uint[] memory input, uint lo, uint hi) view internal {
      uint lo2 = lo;
      uint hi2 = hi;
      if (hi-lo>3){
        uint pivot = input[(hi2+lo2)/2]; // Yeah, this could overflow... but surely the test arrays aren't that long
        while (true){
          while (input[lo2] < pivot){
            lo2 += 1;
          }
          while (input[hi2] > pivot){
            hi2 -= 1;
          }
          if (lo2 >= hi2){
            break;
          }
          (input[lo2], input[hi2]) = (input[hi2], input[lo2]);
          // 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.
          lo2 += 1;
          hi2 -= 1;
        }
        if (lo < hi2){
          quickSort(input, lo, hi2);
        }
        hi2+=1;
        if (hi2 < hi){
          quickSort(input, hi2, hi);
        }
      } else {
        // From wiki:
        // However, insertion sort is one of the fastest algorithms for sorting very small arrays, even faster than quicksort;
        // indeed, good quicksort implementations use insertion sort for arrays smaller than a certain threshold, also when arising
        // as subproblems; the exact threshold must be determined experimentally and depends on the machine, but is commonly around ten.
        uint i = 1;
        while (i < hi-lo+1){
          uint j = lo+i;
            while (j>lo && input[j-1] > input[j]){
              (input[j-1], input[j]) = (input[j], input[j-1]);
              j -=1;
            }
          i+=1;
        }
      }
    }

}