Submission 0ea73040...

ChallengeInteger sorting
Submitterhyszeth.eth
Submitted at2018-05-17
Gas used852123
/**
 * 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 == 0) return input;
        quickSortWithInsertion(input, 0, input.length - 1);
        return input;
     }

    function quickSortWithInsertion(
        uint[] input,
        uint left,
        uint right
    )
        internal
        pure
    {
        uint i = left;
        uint j = right;
        uint a;
        uint b;
        // Run insertion sort on short subarrays
        if (left + 5 > right) {
            for(i = left + 1; i <= right; i++) {
                j = i;
                for(; j > left && (a=input[j-1]) > (b=input[j]); j--) {
                    (input[j], input[j-1]) = (a, b);
                }
            }
            return;
        }
        // Pivot to midpoint
        uint pivot = input[(left + right) / 2];
        // Organize elements above/below pivot
        while (i <= j) {
            while((a=input[i]) < pivot) ++i;
            while(pivot < (b=input[j])) --j;
            if (i <= j) {
                (input[i++], input[j--]) = (b, a);
            }
        }
        // Recurse
        if (left < j) {
            quickSortWithInsertion(input, left, j);
        }
        if (i < right) {
            quickSortWithInsertion(input, i, right);
        }
    }
}