Submission b1f02c1c...

ChallengeInteger sorting
Submittercottenio.eth
Submitted at2018-26-05
Gas used741234
/**
 * 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.
     * Simple QuickSort BENCHMARK
     * Adapted from: https://gist.github.com/subhodi/b3b86cc13ad2636420963e692a4d896f
     *
     * @param input The list of integers to sort.
     * @return The sorted list.
     */
    function sort(uint[] input) public pure returns(uint[]) {
        int n = int(input.length);

        // No need to sort?
        if (n < 2) {
            return input;
        }

        bool sorted = true;
        int i;

        // Is the list already sorted?
        for (i = 1; i < n; i++) {
            if (input[uint(i-1)] > input[uint(i)]) {
                sorted = false;
                break;
            }
        }

        if (sorted) {
            return input;
        }

        // Try reversing the list until a conflict is found
        sorted = true;
        int middle = n / 2;
        for (i = 0; i < middle; i++) {
            if (input[uint(i)] > input[uint(n-i-1)]) {
                (input[uint(i)], input[uint(n-i-1)]) = (input[uint(n-i-1)], input[uint(i)]);
            } else {
                sorted = false;
                break;
            }
        }

        if (sorted) {
            return input;
        }

        // OK, it's probably random
        quickSort(input, 0, n-1);

        return input;
    }

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

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

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

        if (left < j)
            quickSort(arr, left, j);
        if (i < right)
            quickSort(arr, i, right);
    }
}