# Submission bfe99109...

Challenge Integer sorting cottenio.eth 2018-41-28 2320313
``````/**
* This file is part of the 1st Solidity Gas Golfing Contest.
*
*/

pragma solidity 0.4.24;

contract Sort {
uint constant UINT256_MAX = 2**256-1;

/**
* @dev Sorts a list of integers in ascending order.
*
* The input list may be of any length.
* BENCHMARK: Double Pivot QuickSort
*
* @param input The list of integers to sort.
* @return The sorted list.
*/
function sort(uint[] input) public pure returns(uint[]) {
uint n = input.length;

if (n < 2) {
return input;
}

quickSort(input, int(0), int(n-1));

return input;
}

function quickSort(uint[] memory arr, int left, int right) pure internal {
if (left < right) {
int lp;
int rp;
(lp, rp) = partition(arr, left, right);

quickSort(arr, left, lp - 1);
quickSort(arr, lp + 1, rp - 1);
quickSort(arr, rp + 1, right);
}
}

function partition(uint[] memory arr, int left, int right) pure internal returns (int, int) {
if (arr[uint(left)] > arr[uint(right)]) {
swap(arr, left, right);
}

int j = left + 1;
int g = right - 1;
int k = left + 1;
uint p = (arr[uint(left)]);
uint q = (arr[uint(right)]);

while (k <= g) {
if (arr[uint(k)] < p) {
swap(arr, k, j);
j++;
} else if (arr[uint(k)] >= q) {
while (arr[uint(g)] > q && k < g) {
g--;
}

swap(arr, k, g);
g--;

if (arr[uint(k)] < p) {
swap(arr, k, j);
j++;
}
}

k++;
}

j--;
g++;

swap(arr, left, j);
swap(arr, right, g);

return (j, g);
}

function swap(uint[] arr, int a, int b) pure internal {
uint temp = arr[uint(a)];
arr[uint(a)] = arr[uint(b)];
arr[uint(b)] = temp;
}
}

``````