Submission 0a4ed19b...

ChallengeInteger sorting
Submitter0x888888417655103...
Submitted at2018-47-30
Gas used895348
pragma solidity 0.4.24;

contract Sort {

    function sort(
        uint[] input
    ) public pure returns(uint[]) {
        if (input.length == 0) { return; }
        quickSort(input, 0, int(input.length-1));
        return input;
    }

    function choosePivot(
        uint[] input,
        uint head,
        uint tail
    ) internal pure returns (uint) {
        uint middle = (head + tail) / 2;
        if (input[head] < input[middle]) {
            if (input[middle] < input[tail]) {
                return input[middle];
            }
            if (input[head] < input[tail]) {
                (input[middle], input[tail]) = (input[tail], input[middle]);
                return input[middle];
            }
            (input[head], input[middle], input[tail]) = (input[tail], input[head], input[middle]);
            return input[middle];
        }
        if (input[middle] < input[tail]) {
            if (input[head] < input[tail]) {
                (input[head], input[middle]) = (input[middle], input[head]);
                return input[middle];
            }
            (input[head], input[middle], input[tail]) = (input[middle], input[tail], input[head]);
            return input[middle];
        }
        (input[head], input[tail]) = (input[tail], input[head]);
        return input[middle];
    }

    function insertSort(
        uint[] input,
        int head,
        int tail
    ) private pure {
        int j;
        uint tmp;
        for (uint i = uint(head)+1; i <= uint(tail); i++) {
            tmp = input[i];
            j = int(i - 1);
            for (; j >= head; j--) {
                if (tmp > input[uint(j)]) { break; }
                input[uint(j)+1] = input[uint(j)];
            }
            input[uint(j)+1] = tmp;
        }
    }

    function quickSort(
        uint[] input,
        int head,
        int tail
    ) private pure {
        int h = head;
        int t = tail;
        uint pivot = choosePivot(input, uint(h), uint(t));
        while (input[uint(h)] < pivot) { h += 1; }
        while (pivot < input[uint(t)]) { t -= 1; }
        while (h <= t) {
            (input[uint(h++)], input[uint(t--)]) = (input[uint(t)], input[uint(h)]);
            while (input[uint(h)] < pivot) { h += 1; }
            while (pivot < input[uint(t)]) { t -= 1; }
        }
        if (t - head > 8) {
            quickSort(input, head, t);
        } else if (t > head) {
            insertSort(input, head, t);
        }
        if (tail - h > 8) {
            quickSort(input, h, tail);
        } else if (tail > h) {
            insertSort(input, h, tail);
        }
    }
}