Submission b4364476...

ChallengeInteger sorting
Submitter0x888888417655103...
Submitted at2018-34-30
Gas used908788
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 (h <= t) {
            while (input[uint(h)] < pivot) { h += 1; }
            while (pivot < input[uint(t)]) { t -= 1; }
            if (h <= t) {
                (input[uint(h++)], input[uint(t--)]) = (input[uint(t)], input[uint(h)]);
            }
        }
        if (head < t) {
            if (t - head <= 8 && head != 0) {
                insertSort(input, head, t);
            } else {
                quickSort(input, head, t, input[uint((head + t) / 2)]);
            }
        }
        if (h < tail) {
            if (tail - h <= 8) {
                insertSort(input, h, tail);
            } else {
                quickSort(input, h, tail, input[uint((h + tail) / 2)]);
            }
        }
    }
}