def binary_insertion_sort(items: list) -> list:
    """

    Complexity:
        Time: O(n^2)
        Space: O(1)

        NOTE: since shifting dominates the runtime,
        allowing binary search subroutine to be Θ(logn)
        by not breaking early if `items[mid_idx] == insertion_val`.

        This minimizes shift operations by ensuring
        `items[mid_idx]` is the smallest element *strictly* greater
        than `insertion_val` (i.e., the IMMEDIATE SUCCESSOR)

        See Also:
            - pytudes/_2021/educative/modified_binary_search/_3__next_letter__medium.py

    Args:
        items:

    Returns: `items` sorted

    Examples:
        >>> binary_insertion_sort([5,4,3,2,1,0])
        [0, 1, 2, 3, 4, 5]
        >>> binary_insertion_sort([0,1,2,3,4,5])
        [0, 1, 2, 3, 4, 5]
        >>> binary_insertion_sort([5,4,3,2,1,0]*2)
        [0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5]
        >>> items = [random.randrange(0, 100) for _ in range(100)]
        >>> assert(binary_insertion_sort(items.copy()) == sorted(items))

    """

    for unsorted_start_idx in range(1, len(items)):
        ## Minor optimization to ensure Ω(n) (i.e., already sorted arrays)
        sorted_end_idx = unsorted_start_idx - 1
        insertion_val = items[unsorted_start_idx]
        if items[sorted_end_idx] <= insertion_val:  # Already in sorted order
            continue

        ## BINARY SEARCH for insertion idx ##
        left, right = 0, sorted_end_idx
        while left <= right:
            mid_idx = (left + right) // 2
            if insertion_val < items[mid_idx]:  # Search LEFT
                right = mid_idx - 1
            else:  # insertion_val >= items[mid_idx] # Search RIGHT
                left = mid_idx + 1
        insertion_idx = left
        # items[left] is now IMMEDIATE SUCCESSOR of insertion_val
        #   See Also: pytudes/_2021/miscellany/searching/binary_search.py:19

        ## BISECT LEFT ##
        # Shift right items in the range [insertion_idx, len(items))
        # and insert `insertion_val` at `insertion_idx`
        for src_idx in reversed(range(insertion_idx, unsorted_start_idx)):
            items[src_idx + 1] = items[src_idx]
        items[insertion_idx] = insertion_val

    return items