Solidity implementation of max-heapsort

HeapSort.sol

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;

contract HeapSort {
    function sort(uint256[] calldata _input) external pure returns (uint256[] memory) {
        _buildMaxHeap(_input);

        uint256 length = _input.length;
        unchecked {
            for (uint256 i = length - 1; i > 0; --i) {
                _swap(_input, 0, i);
                _heapify(_input, i, 0);
            }
        }

        return _input;
    }

    function _buildMaxHeap(uint256[] memory _input) internal pure {
        uint256 length = _input.length;

        unchecked {
            for (uint256 i = (length >> 1) - 1; i > 0; --i) {
                _heapify(_input, length, i);
            }
            _heapify(_input, length, 0);
        }
    }

    function _heapify(uint256[] memory _input, uint256 _n, uint256 _i) internal pure {
        unchecked {
            uint256 max = _i;
            uint256 left = (_i << 1) + 1;
            uint256 right = (_i << 1) + 2;

            if (left < _n && _input[left] > _input[max]) {
                max = left;
            }

            if (right < _n && _input[right] > _input[max]) {
                max = right;
            }

            if (max != _i) {
                _swap(_input, _i, max);
                _heapify(_input, _n, max);
            }
        }
    }

    function _swap(uint256[] memory _input, uint256 _i, uint256 _j) internal pure {
        (_input[_i], _input[_j]) = (_input[_j], _input[_i]);
    }
}