Submission 3ce9e9bb...

ChallengeInteger sorting
Submitter0xd0b40847c318da4...
Submitted at2018-25-10
Gas used1482425
/**
 * 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 <= 1) {
            return input;
        }
        quickSort(input, 0, input.length - 1);
        return input;
    }

    function quickSort(uint[] a, uint lo, uint hi) internal pure {
        if (lo >= hi)
            return;

        if (hi - lo == 1) {
            if (a[hi] < a[lo]) {
                (a[lo], a[hi]) = (a[hi], a[lo]);
            }
            return;
        }

        if (hi - lo <= 6) {
            insertionSort(a, lo, hi);
            return;
        }

        uint p = partition(a, lo, hi);
        if (p > lo) {
            quickSort(a, lo, p-1);
        }
        if (p < hi) {
            quickSort(a, p+1, hi);
        }
    }

    function insertionSort(uint[] a, uint lo, uint hi) internal pure {
        uint low;
        for (uint i = lo; i < hi; i++) {
            low = i;
            for (uint j = i+1; j <= hi; j++) {
                if (a[j] < a[low]) {
                    low = j;
                }
            }
            if (low != i) {
                (a[i], a[low]) = (a[low], a[i]);
            }
        }
    }

    function median(uint[] a, uint x, uint y, uint z) internal pure {
        (uint X, uint Y, uint Z) = (a[x], a[y], a[z]);
        if (X > Y) {
          if (Y > Z) {
            (a[x], a[y]) = (Y, X);
          } else if (X > Z) {
            (a[x], a[z]) = (Z, X);
          }
        } else {
          if (X > Z) {
          } else if (Y > Z) {
            (a[x], a[z]) = (Z, X);
          } else {
            (a[x], a[y]) = (Y, X);
          }
        }
    }

    function partition(uint[] a, uint lo, uint hi) internal pure returns (uint) {
        median(a, lo, (lo + hi) / 2, hi);

        (uint pivot, uint i, uint j) = (a[lo], lo+1, hi);
        while (true) {
            while (i <= j && a[i] <= pivot) {
                i++;
            }

            while (i <= j && a[j] > pivot) {
                j--;
            }

            if (j < i) {
                (a[lo], a[j]) = (a[j], a[lo]);
                return j;
            }

            (a[i], a[j]) = (a[j], a[i]);
        }
    }
}