I also renamed _is_sorted_by_data into _is_sorted_by_row_values for consistency with the new function sort_by_row_values. Do you think it would make sense to also make the function _is_sorted_by_row_values public?

Thanks for the comments!
Any opinion on making _is_sorted_by_row_values public as well?

Any opinion on making _is_sorted_by_row_values public as well?

I think the most common use case would be how we use it in _check_precomputed. If it is public, we would kind of force everyone to work on csr matrices because is_graph_sorted_by_row_values only works on CSRs.

graph = check_array(graph, accept_sparse="csr")
if not is_graph_sorted_by_row_values(graph):
    graph = sort_graph_by_row_values(graph)

In this case, we can not stop users from starting off with a graph that is bsr, dok or dia.

What if we put the is_graph_sorted_by_row_values check inside of sort_graph_by_row_values?

def sort_graph_by_row_values(graph, copy=False, warn_when_not_sorted=True):
    # check for accepted graph formats
    if is_graph_sorted_by_row_values(graph):
         return graph

    # Maybe always warn?
    if warn_when_not_sorted:
        warnings.warn(...)

    if graph.format != "csr":
        graph = graph.asformat("csr")
    elif copy:
        graph = graph.copy()
    
    # sort graph by rows
    return graph

This is similar to what you had before, but with the extra is_graph_sorted_by_row_values inside sort_graph_by_row_values.

What if we put the is_graph_sorted_by_row_values check inside of sort_graph_by_row_values?

I like it, see my latest commit.

Thanks @TomDLT all good.