def insertion_sort_transformer(
    circuit: cirq.AbstractCircuit, *, context: cirq.TransformerContext | None = None
) -> cirq.Circuit:
    """Sorts the operations using their sorted `.qubits` property as comparison key.

    Operations are swapped only if they commute.

    Args:
        circuit: input circuit.
        context: optional TransformerContext (not used),
    """
    final_operations: list[cirq.Operation] = []
    qubit_index: dict[cirq.Qid, int] = {
        q: idx for idx, q in enumerate(sorted(circuit.all_qubits()))
    }
    cached_qubit_indices: dict[int, list[int]] = {}
    for pos, op in enumerate(circuit.all_operations()):
        # here `pos` is at the append position of final_operations
        if (op_qubit_indices := cached_qubit_indices.get(id(op))) is None:
            op_qubit_indices = cached_qubit_indices[id(op)] = sorted(
                qubit_index[q] for q in op.qubits
            )
        for tail_op in reversed(final_operations):
            tail_qubit_indices = cached_qubit_indices[id(tail_op)]
            if op_qubit_indices < tail_qubit_indices and (
                # special case for zero-qubit gates
                not op_qubit_indices
                # check if two sorted sequences are disjoint
                or op_qubit_indices[-1] < tail_qubit_indices[0]
                or set(op_qubit_indices).isdisjoint(tail_qubit_indices)
                # fallback to more expensive commutation check
                or protocols.commutes(op, tail_op, default=False)
            ):
                pos -= 1
                continue
            break
        final_operations.insert(pos, op)
    return circuits.Circuit(final_operations)
Sorts the operations using their sorted `.qubits` property as comparison key.

    Operations are swapped only if they commute.

    Args:
        circuit: input circuit.
        context: optional TransformerContext (not used),
    
cirq-core/cirq/transformers/insertion_sort.py