Submission 205e969d...

ChallengeInteger sorting
Submitterhyszeth.eth
Submitted at2018-53-16
Gas used892729
/**
 * 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/
 *
 * Author: Greg Hysen (@hysz)
 * Date: June, 2018
 */

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 == 0) return input;
        quickSort(input, 0, input.length - 1);
        //insertionSort(input, 0, input.length - 1);
        return input;
     }

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

                if(i >= j) break;
                (input[uint(i)], input[uint(j)]) = (input[uint(j)], input[uint(i)]);
            }

            if(lo < j) {
                if(j - lo > 5) quickSort(input, lo, j);
                else insertionSort(input, lo, j);
            }
            j++;
            if(j < hi) {
                if(hi - j > 5) quickSort(input, j, hi);
                else insertionSort(input, j, hi);
            }
        }

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