Submission 3f5e51a5...

Challenge	Integer sorting
Submitter	ricmoo.firefly.eth
Submitted at	2018-10-31
Gas used	1531359

contract Sort {

    function sort(uint[] input) public pure returns(uint[]) {
        uint length = input.length;
        if (length <= 1) { return input; }

        uint i;

        // Count ordered elements
        uint asc = 0;
        for (i = length - 1; i > 0; i--) {
            if (input[i] >= input[i - 1]) { asc++; }
        }

        // If Almost entirely reversed, reverse it
        if (asc < (length / 4)) {
            uint end = length / 2;
            for (i = 0; i < end; i++) {
                (input[i], input[length - i - 1]) = (input[length - i - 1], input[i]);
                //uint tmp = input[i];
                //input[i] = input[length - i - 1];
                //input[length - i - 1] = tmp;
            }
            asc = length - asc - 1;
        }

        // Already sorted
        if ((asc + 1) == length) { return input; }

        // If less than 16 things are already sorted...
        // @TODO: Build testcases to find an imperical value that is good...
        if (asc + 16 < length) {
            /*
            // Not needed anymore; mostly sorted lists are handled by linear insertion sort
            // Fisher-Yates Shuffle
            uint accum = 0xb7adaa22903e58e3f323d2f70f87e0eeb5d6447027b9f9eab9df7cbcab31f4e4;
            for (uint i = length - 1; i > 1; i--) {
                uint a = input[i];
                accum ^= a;
                uint j = accum % (i + 1);
                input[i] = input[j];
                input[j] = a;
            }
            */

            // QuickSort
            sort(input, 0, uint(length - 1));

        } else {

            // Linear Insertion Sort
            // See: https://en.wikipedia.org/wiki/Insertion_sort
            for (i = 1; i < length; i++) {
                uint256 tmp = input[i];
                int256 j = int(i) - 1;
                while (j >= 0 && input[uint(j)] > tmp) {
                    input[uint(j) + 1] = input[uint(j)];
                    j--;
                }
                input[uint(j) + 1] = tmp;
            }
        }

        return input;
    }

    // Quick Sort (Hoare partition scheme)
    // See: https://en.wikipedia.org/wiki/Quicksort
    function sort(uint[] A, uint lo, uint hi) internal pure {
        if (lo < hi) {
            uint p = partition(A, lo, hi);
            sort(A, lo, p);
            sort(A, p + 1, hi);
        }
    }

    function partition(uint[] A, uint lo, uint hi) internal pure returns (uint) {
        uint pivot = A[uint(lo)];

        // Note: May temporarility overflow below 0, but will be corrected in the first loop
        uint i = lo - 1;
        uint j = hi + 1;
        while (true) {
            while(true) {
                i++;
                if (A[uint(i)] >= pivot) { break; }
            }
            while(true) {
                j--;
                if (A[uint(j)] <= pivot) { break; }
            }

            if (i >= j) { return j; }

            (A[uint(i)], A[uint(j)]) = (A[uint(j)], A[uint(i)]);
        }
    }

}