RadixSort.sol

// SPDX-License-Identifier: MIT
pragma solidity >=0.8.4;

library RadixSort {
    uint256 internal constant ALPHABET_SIZE_LOG_2 = 7;
    uint256 internal constant ALPHABET_SIZE = 1 << ALPHABET_SIZE_LOG_2;
    uint256 internal constant MASK = ALPHABET_SIZE - 1;

    function sort(uint256[] memory _list) internal pure {
        uint256 iterations;
        assembly {
            iterations := add(div(256, ALPHABET_SIZE_LOG_2), 1)
        }

        unchecked {
            for (uint256 i; i < iterations; ++i) {
                countSort(_list, i);
            }
        }
    }

    function countSort(uint256[] memory _input, uint256 _offset) internal pure {
        uint256[ALPHABET_SIZE] memory counts;
        uint256 length = _input.length;
        uint256[] memory temp = new uint256[](length);

        unchecked {
            for (uint256 i; i < length; ++i) {
                counts[(_input[i] >> (_offset * ALPHABET_SIZE_LOG_2)) & MASK]++;
            }

            for (uint256 i = 1; i < ALPHABET_SIZE; ++i) {
                counts[i] += counts[i - 1];
            }

            for (uint256 i = length - 1; i > 0; --i) {
                temp[--counts[(_input[i] >> (_offset * ALPHABET_SIZE_LOG_2)) & MASK]] = _input[i];
            }
            temp[--counts[(_input[0] >> (_offset * ALPHABET_SIZE_LOG_2)) & MASK]] = _input[0];

            for (uint256 i; i < length; ++i) {
                _input[i] = temp[i];
            }
        }
    }
}