Submission 96e4ac8e...

ChallengeInteger sorting
Submitterhyszeth.eth
Submitted at2018-38-17
Gas used812648
/**
 * 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);
        return input;
     }

    function quickSort(
        uint[] input,
        uint lo,
        uint hi
    )
     internal
     pure
    {
        // Pivot (Median of 3)
        i = uint((hi+lo)/2); // pivot index
        uint pivot = input[i];
        if((iElem=input[lo]) > pivot) {
            (input[lo], input[i]) = (pivot, iElem);
            pivot = iElem;
        }
        if((iElem=input[lo]) > (jElem=input[hi])) (input[lo], input[hi]) = (jElem, iElem);
        if((iElem=input[i]) > (jElem=input[hi])) {
            (input[i], input[hi]) = (jElem, iElem);
            pivot = jElem;
        }

        // Hoare pivot algorithm
        uint i = lo - 1;
        uint j = hi + 1;
        uint iElem;
        uint jElem;
        while(true) {
            while((iElem=input[uint(++i)]) < pivot) {}
            while((jElem=input[uint(--j)]) > pivot) {}

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

        // Sort
        i = j - lo;
        if(i > 11) quickSort(input, lo, j);
        else if(i > 1) insertionSort(input, lo, j);

        i = hi - ++j;
        if(i > 11) quickSort(input, j, hi);
        else if(i > 1) insertionSort(input, j, hi);
    }

    function insertionSort(
        uint[] input,
        uint lo,
        uint hi
    )
     internal
     pure
    {
        // If within threshold, run insertion sort instead.
        uint i = lo + 1;
        while(i <= hi) {
            uint j = i;
            uint jElem=input[j];
            uint iElem;
            while(j > lo && (iElem=input[j-1]) > jElem) {
                input[j--] = iElem;
            }
            if(j != i++) input[j] = jElem;
        }
    }
}