Submission e9c7c0ac...

ChallengeInteger sorting
Submittercottenio.eth
Submitted at2018-38-30
Gas used1090820
/**
 * 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 {
    uint constant UINT256_MAX = 2**256-1;

    /**
     * @dev Sorts a list of integers in ascending order.
     *
     * The input list may be of any length.
     * BENCHMARK: QuickSort with reversal scan
     *
     * @param input The list of integers to sort.
     * @return The sorted list.
     */
    function sort(uint[] input) public pure returns(uint[]) {
        uint n = input.length;

        if (n < 2) {
            return input;
        }

        bool good = false;
        uint prev = 0;
        uint p = n / 2;

        if (input[i] > input[i+1]) {
            good = true;
            for (uint i = 0; i < p; i++) {
                (input[i], input[n-i-1]) = (input[n-i-1], input[i]);
                if (input[i] < prev) {
                    good = false;
                    break;
                } else {
                    prev = input[i];
                }
            }
        }

        if (!good) {
            quickSort(input, 0, n-1);
        }

        return input;
    }

    function quickSort(uint[] memory arr, uint left, uint right) pure internal {
        uint i = left;
        uint j = right;

        uint pivot = arr[(left + (right - left) / 2)];

        while (i <= j && j != UINT256_MAX) {
            while (arr[i] < pivot) i++;
            while (pivot < arr[j]) j--;
            if (i <= j) {
                (arr[i], arr[j]) = (arr[j], arr[i]);
                i++;
                j--;
            }
        }

        if (left < j && j != UINT256_MAX)
            quickSort(arr, left, j);
        if (i < right)
            quickSort(arr, i, right);
    }
}