๐ŸŽ“ A1Learner
๐Ÿ”

Rust Parallel Sorting

Parallel sorting sorts a slice across many cores. Rayon splits the slice into parts, sorts each part on its own core, and then merges the parts into one sorted slice.

par_sort sorts the whole slice

The call replaces sort. The result is the same.

let mut nums = vec![5, 2, 8, 1, 9, 3];
nums.par_sort();
println!("sorted = {:?}", nums);

Words sort too

Any slice of sortable values works. Strings sort by their letters.

let mut names = vec!["Mia", "Ava", "Zoe", "Eli"];
names.par_sort();
println!("names = {:?}", names);

unstable may swap equals

Equal values may change places. Pick it when equal values are identical anyway.

let mut nums = vec![7, 3, 7, 1];
nums.par_sort_unstable();
println!("sorted = {:?}", nums);

Sort by a key

The key is drawn from each value. Equal keys keep their first order.

let mut words = vec!["pear", "fig", "banana", "kiwi"];
words.par_sort_by_key(|w| w.len());
println!("by length = {:?}", words);

Sort by your own rule

par_sort_by takes a compare closure. Flip the inputs and the sort flips.

let mut nums = vec![3, 9, 1, 5];
nums.par_sort_by(|a, b| b.cmp(a));
println!("biggest first = {:?}", nums);

Example

// Cargo.toml: rayon = "1"
use rayon::prelude::*;

fn main() {
    let mut nums = vec![42, 7, 13, 7, 99, 0, 55, 23, 7, 61, 8, 30];
    nums.par_sort();
    println!("sorted = {:?}", nums);

    let mut names = vec!["banana", "fig", "cherry", "date"];
    names.par_sort_by_key(|name| name.len());
    println!("by length = {:?}", names);
}

Key points

  • par_sort is stable.
  • Equal values keep their original order.
  • par_sort_unstable may reorder equal values.
  • It skips that bookkeeping.
  • It is often a little faster.
  • Use par_sort_by_key to sort by a value drawn from each item.
  • Use par_sort_by to compare two items your own way.
  • Parallel sorting pays on big data.
  • A short Vec sorts fast enough on one core.
  • Splitting it only adds cost.
  • The answer is the same sorted slice that sort() would give.
  • Parallel sorting divides a slice, sorts the parts at the same time, and merges them into one sorted slice.

In this example, one Vec holds twelve numbers. par_sort puts them in order. Three copies of 7 stay together in the middle. Then four words sort by length. fig has three letters. date has four. banana and cherry both have six. banana came first in the input. The stable sort keeps it first.

Note

Rayon only changes how the work is shared.

Try it Yourself

Edit the code, then press Run.

Running is simulated ยท Rust Playground

Exercise

When is par_sort a poor choice?