Sorting array of pointers

I have data stored spread out (x and y in the example below) and I want to sort them relative to each other.
Is this somehow possible with the stdlib or do I need to write my own sorting algorithm?

fn sort_references<T: Ord>(arr: &mut [&mut T]) {
    todo!();
    // sort by writing to the underlying data, not swap pointers in array
}

#[test]
fn tests() {
    let mut x = 2;
    let mut y = 1;
    sort_references(&mut [&mut x, &mut y]);
    assert_eq!(x, 1);
    assert_eq!(y, 2);
}
  • T is not necessarily Clone
  • The arrays are quite small (<50 elements) but dynamic in size

I think you'll need your own. [1]

Incidentally by sorting the objects directly in the slice, the std implementation can move ranges of elements all at once with a memcpy. You would need reads and writes for each element.

So the ideal algorithm is probably different anyway.


  1. Alternatively you could sort some wrapper that remembers source index and then figure out how to swap things around afterwards, but that doesn't seem any nicer to me. ↩︎

1 Like

I read the internal code a bit and saw this: rust/sort.rs at bbdca4c28fd9b57212cb3316ff4ffb1529affcbe · rust-lang/rust · GitHub
Blocking seems quite smart here.

Wrapper with index seems reasonable for my use case, although the swaping might not be a trivial algorithm as well :sweat_smile: (probably chase cycles)

Yeah, it's "keep track of unseen indices and chase cycles" or so.

Naive (but no unsafe) version.

1 Like

Very cool!
Small suggestion: using Vec<bool> or bit_vec should save some hashing and HashSet growing operations.

Like this.

Incorporating the ideas from sorting - How to sort a vector by indices in Rust - Stack Overflow

and fore-going the 2nd extra allocation for the permutation we obtain this:

It almost seems just as easy to implement a sorting algorithm from scratch. Here is heap-sort:

2 Likes