Why does sorting take so long?

Question

I am currently trying to learn the syntax of Rust by solving little tasks. I compare the execution time as sanity-checks if I am using the language the right way.

One task is:

1. Create an array of 10000000 random integers in the range 0 - 1000000000
2. Sort it and measure the time
3. Print the time for sorting it

I got the following results:

| #   | Language             | Speed  | LOCs |
| --- | -------------------- | ------ | ---- |
| 1   | C++ (with -O3)       | 1.36s  | 1    |
| 2   | Python (with PyPy)   | 3.14s  | 1    |
| 3   | Ruby                 | 5.04s  | 1    |
| 4   | Go                   | 6.17s  | 1    |
| 5   | C++                  | 7.95s  | 1    |
| 6   | Python (with Cython) | 11.51s | 1    |
| 7   | PHP                  | 36.28s | 1    |

Now I wrote the following Rust code:

rust.rs

extern crate rand;
extern crate time;

use rand::Rng;
use time::PreciseTime;

fn main() {
    let n = 10000000;
    let mut array = Vec::new();

    let mut rng = rand::thread_rng();
    for _ in 0..n {
        //array[i] = rng.gen::<i32>();
        array.push(rng.gen::<i32>());
    }

    // Sort
    let start = PreciseTime::now();
    array.sort();
    let end = PreciseTime::now();

    println!("{} seconds for sorting {} integers.", start.to(end), n);
}

with the following Cargo.toml:

[package]
name = "hello_world" # the name of the package
version = "0.0.1"    # the current version, obeying semver
authors = [ "[email protected]" ]
[[bin]]
name = "rust"
path = "rust.rs"
[dependencies]
rand = "*" # Or a specific version
time = "*"

I compiled it with cargo run rust.rs and ran the binary. It outputs

PT18.207168155S seconds for sorting 10000000 integers.

Note that this is much slower than Python. I guess I am doing something wrong. (The complete code of rust and of the other languages is here if you are interested.)

Why does it take so long to sort with Rust? How can I make it faster?

Answer 1

I Tried your code on my computer, running it with cargo run gives:

PT11.634640178S seconds for sorting 10000000 integers.

And with cargo run --release (turning on optimizations) gives:

PT1.004434739S seconds for sorting 10000000 integers.