Submission 490f4e3e...

ChallengeInteger sorting
Submitter0x888888417655103...
Submitted at2018-23-29
Gas used897681
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), input[(input.length-1)/2]);
        return input;
    }

    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,
        uint pivot
    ) private pure {
        int h = head;
        int t = tail;
        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, input[uint((head + t) / 2)]);
        } else if (t > head) {
            insertSort(input, head, t);
        }
        if (tail - h > 8) {
            quickSort(input, h, tail, input[uint((h + tail) / 2)]);
        } else if (tail > h) {
            insertSort(input, h, tail);
        }
    }
}