Sort by parity in rust

Question

I am learning sorting in rust. I want to sort vector as such that even numbers go first

My code is OK. But can it be improved (I want to use sort function)?

fn main() {
 let mut v = vec![1, 2, 10, 4, 3];
 v.sort_by(|a, b | {
 (a % 2).cmp(&(b % 2))
 });
 println!("{:?}", v); // [1, 2, 10, 4, 3]
}
 

• J_H: Looks good to me. But that's an odd comparison function, which discards all the high-order bits. You're sure you wouldn't care to use magnitude as a tie breaker? I mean, you have the first half of a bucket sort, assigning to one of two buckets. But the "sort within bucket" part is missing.
• Chayim Refael Friedman: v.sort_by_key(|v| v % 2)

Answer 1

Partition the Array

This is the standard example of std::iter::Iterator::partition. There is also a nightly experimental partition_in_place.

let (even, odd): (Vec<_>, Vec<_>) = a
 .into_iter()
 .partition(|n| n % 2 == 0);

This runs in O(N) time, while sorting takes O(N log N) time.

If you want the even and odd collections to be sorted (which this doesn’t do), it’s more efficient to partition and then sort the sub-arrays. Sorting has worse-than-linear time complexity, so it’s better to sort two partitions than one large array.

Answer 2

x % 2 has a nasty pitfall

And it results in a bug this time.

How much is -1 % 2? It couldn't be 0 of course, but it's also not 1. Not in Rust anyway, it does vary by language.

With this data: let mut v = vec![1, 2, 10, 4, 3, -1, -2, -3];, I get this result:

[-1, -3, 2, 10, 4, -2, 1, 3]

Probably not what you want.

On the other hand, x & 1 properly results in 0 for even numbers and 1 for odd numbers, positive or negative.

Using x % 2 to decide even/odd is not always wrong. If the result is compared to zero, it doesn't matter that odd numbers sometimes result in +1 and sometimes in -1, either way the result isn't zero. That's why Davislors answer doesn't suffer from this bug, despite using n % 2.

• L. F.: Or x.rem_euclid(2).
• Davislor: Rustc with release flags optimizes n%2 == 0, into a bitwise and, automatically. So, yes, they’re equivalent.
• Davislor: Also, like I said in my answer, that’s not my code. It’s an example from the Rust standard library documentation I linked to.
• Davislor: But, flattered that you’d give me credit for it!