Submission bfe99109...

ChallengeInteger sorting
Submittercottenio.eth
Submitted at2018-41-28
Gas used2320313
/**
 * 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: Double Pivot QuickSort
     *
     * @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;
        }

        quickSort(input, int(0), int(n-1));

        return input;
    }

    function quickSort(uint[] memory arr, int left, int right) pure internal {
        if (left < right) {
            int lp;
            int rp;
            (lp, rp) = partition(arr, left, right);

            quickSort(arr, left, lp - 1);
            quickSort(arr, lp + 1, rp - 1);
            quickSort(arr, rp + 1, right);
        }
    }

    function partition(uint[] memory arr, int left, int right) pure internal returns (int, int) {
        if (arr[uint(left)] > arr[uint(right)]) {
            swap(arr, left, right);
        }

        int j = left + 1;
        int g = right - 1;
        int k = left + 1;
        uint p = (arr[uint(left)]);
        uint q = (arr[uint(right)]);

        while (k <= g) {
            if (arr[uint(k)] < p) {
                swap(arr, k, j);
                j++;
            } else if (arr[uint(k)] >= q) {
                while (arr[uint(g)] > q && k < g) {
                    g--;
                }

                swap(arr, k, g);
                g--;

                if (arr[uint(k)] < p) {
                    swap(arr, k, j);
                    j++;
                }
            }

            k++;
        }

        j--;
        g++;

        swap(arr, left, j);
        swap(arr, right, g);

        return (j, g);
    }

    function swap(uint[] arr, int a, int b) pure internal {
        uint temp = arr[uint(a)];
        arr[uint(a)] = arr[uint(b)];
        arr[uint(b)] = temp;
    }
}