Sort: linear time for already sorted list?

help
1

Is there a sorting algorithm on a Rust Vec with the following property:

  1. if the list of already sorted, i.e. v[i] <= v[i+1] for the specified Cmp operator, then it only takes O(n) time (instead of O(n log n))

  2. for nearly sorted list (for some formal definition), it takes only nearly linear time ?

2

This is called an adaptive sort algorithm. The timsort sorting algorithm has this property. It is the algorithm used by the Rust standard library for slice::sort. From the documentation:

The current algorithm is an adaptive, iterative merge sort inspired by timsort. It is designed to be very fast in cases where the slice is nearly sorted, or consists of two or more sorted sequences concatenated one after another.

3

And, as a proof:

use std::time::Instant;

fn main() {
    for n in (1 << 16..1 << 20).step_by(1 << 16) {
        let mut v = (0..n).collect::<Vec<_>>();
        let tic = Instant::now();
        v.sort();
        println!(
            "{n}: {:?}/item",
            (Instant::now() - tic).as_secs_f64() / n as f64
        );
    }
}

yields the output:

65536: 5.049896240234375e-10/item
131072: 4.8614501953125e-10/item
196608: 4.747873942057291e-10/item
262144: 4.749832153320312e-10/item
327680: 4.723968505859375e-10/item
393216: 5.158309936523438e-10/item
458752: 4.938310895647321e-10/item
524288: 5.193080902099609e-10/item
589824: 5.492621527777777e-10/item
655360: 5.307754516601562e-10/item
720896: 5.408255837180398e-10/item
786432: 6.040776570638021e-10/item
851968: 6.330108642578125e-10/item
917504: 6.104093279157367e-10/item
983040: 6.078399658203125e-10/item

So slice::sort is quite reliable when it comes to sorting already-sorted arrays. Note that sort_unstable() is even faster, so you should use that when you get the chance.