How do I check if a slice is sorted?

I'd grab pairs of elements and assert they are all in ascending (or descending, depending on what you mean by "sorted") order:

fn is_sorted<T>(data: &[T]) -> bool
where
    T: Ord,
{
    data.windows(2).all(|w| w[0] <= w[1])
}

fn main() {
    assert!(is_sorted::<u8>(&[]));
    assert!(is_sorted(&[1]));
    assert!(is_sorted(&[1, 2, 3]));
    assert!(is_sorted(&[1, 1, 1]));
    assert!(!is_sorted(&[1, 3, 2]));
    assert!(!is_sorted(&[3, 2, 1]));
}

Ditto for generic iterators:

extern crate itertools; // 0.7.8

use itertools::Itertools;

fn is_sorted<I>(data: I) -> bool
where
    I: IntoIterator,
    I::Item: Ord + Clone,
{
    data.into_iter().tuple_windows().all(|(a, b)| a <= b)
}

fn main() {
    assert!(is_sorted(&[] as &[u8]));
    assert!(is_sorted(&[1]));
    assert!(is_sorted(&[1, 2, 3]));
    assert!(is_sorted(&[1, 1, 1]));
    assert!(!is_sorted(&[1, 3, 2]));
    assert!(!is_sorted(&[3, 2, 1]));
}

See also:

  • Are there equivalents to slice::chunks/windows for iterators to loop over pairs, triplets etc?

In nightly Rust, there are unstable methods to accomplish this:

  • slice::is_sorted
  • slice::is_sorted_by
  • slice::is_sorted_by_key
  • Iterator::is_sorted
  • Iterator::is_sorted_by
  • Iterator::is_sorted_by_key

One more using try_fold():

pub fn is_sorted<T: IntoIterator>(t: T) -> bool
where
    <T as IntoIterator>::Item: std::cmp::PartialOrd,
{
    let mut iter = t.into_iter();

    if let Some(first) = iter.next() {
        iter.try_fold(first, |previous, current| {
            if previous > current {
                Err(())
            } else {
                Ok(current)
            }
        })
        .is_ok()
    } else {
        true
    }
}

It is not necessary to have Clone for an iterator is_sorted implementation. Here is a no-dependency Rust implementation of is_sorted:

fn is_sorted<I>(data: I) -> bool
where
    I: IntoIterator,
    I::Item: Ord,
{
    let mut it = data.into_iter();
    match it.next() {
        None => true,
        Some(first) => it.scan(first, |state, next| {
            let cmp = *state <= next;
            *state = next;
            Some(cmp)
        }).all(|b| b),
    }
}