InsertionSort.sol

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

library InsertionSort {
    function sort(uint256[] memory list) internal pure {
        // Algorithm:
        //
        // for i = 2 to n do
        //   for j = 1 to i − 1 do // NOTE: we init do an extra sub instead of <=
        //     if A[i] < A[j] then
        //       swap A[i] and A[j]
        assembly ("memory-safe") {
            let len := add(1, mload(list))
            let firstElem := add(0x20, list)

            for { let i := 2 } lt(i, len) { i := add(i, 1) } {
                let idx := sub(i, 1)
                for { let j := 0 } lt(j, idx) { j := add(j, 1) } {
                    let a_i_ptr := add(firstElem, shl(5, idx))
                    let a_j_ptr := add(firstElem, shl(5, j))
                    let a_i := mload(a_i_ptr)
                    let a_j := mload(a_j_ptr)
                    switch lt(a_i, a_j)
                    case 1 {
                        mstore(a_j_ptr, a_i)
                        mstore(a_i_ptr, a_j)
                    }
                }
            } 
        }
    }
}