Helping people with "broken" sorting

Ideas
29

I don’t fully understand why this needs to be cubic.

I’d gather we need to compare all pairs in the sequence, so quadratic. If you imagine them in a matrix, all values in the lower triangle need to compare less than the diagonal, and the diagonal is less than all values in the upper triangle.

For y as diagonal, x in the lower triangle, and z in the upper triangle, this is implemented in below nested generator comprehension:

def is_total_order[T: annotated_types.SupportsLe](seq: Sequence[T], /) -> bool:
    return all(all(x <= y for x in seq[: j])          # all `x` left of `y` must compare before `y`
               and all(y <= z for z in seq[j + 1 :])  # `y` must compare before all `z` right of `y`
               for j, y in enumerate(seq)             # for all `y` in `seq`
               )

(note the slicing makes for clear code, but would impact performance (unless seq is a sequence view); @blhsing’s index-based approach with i, j, k would perform better).

But perhaps I’m missing something and cubic is necessary. Please explain then.

1 Like