DEV Community

Juraj K.
Juraj K.

Posted on

Is sleep-sort actually bad?

Today, I am testing sleep-sort. But not just any sleep-sort. I am speeding it up!

High Speed

Before I begin, let me explain what sleep-sort actually is.

Sleep sort creates multiple threads for all items to sort. It sleeps the value of the item in the list.

Sleep

For example, we have this list:

list = [1, 3, 2]
Enter fullscreen mode Exit fullscreen mode

This is how it will work:

Example

Now, this is about how it will print:

1
2
3
Enter fullscreen mode Exit fullscreen mode

The way I am speeding it up is this guy.

Division

We can divide the number of the item in the list. I asked Gemini for a quick sleep-sort code in the slowest languague in the world.

We have this:

import threading
import time

# A list to store the sorted numbers
_sorted_list = []
_lock = threading.Lock()

def _sleep_and_append(num):
    """
    A helper function for the thread to sleep for 'num' seconds
    and then append the number to the sorted list.
    """
    time.sleep(num)
    with _lock:
        _sorted_list.append(num)

def sleepsort(numbers):
    """
    Sorts a list of numbers using the sleep sort algorithm.
    This function is for demonstration and is not practical.
    """
    global _sorted_list
    _sorted_list = []

    threads = []
    for num in numbers:
        thread = threading.Thread(target=_sleep_and_append, args=(num,))
        threads.append(thread)
        thread.start()

    # Wait for all threads to complete
    for thread in threads:
        thread.join()

    return _sorted_list

if __name__ == '__main__':
    # Example usage
    numbers_to_sort = [5, 2, 8, 1, 9, 4]
    print(f"Original list: {numbers_to_sort}")

    sorted_numbers = sleepsort(numbers_to_sort)
    print(f"Sorted list: {sorted_numbers}")

    # Another example
    numbers_to_sort_2 = [3.1, 0.5, 4.2, 2.0]
    print(f"\nOriginal list: {numbers_to_sort_2}")

    sorted_numbers_2 = sleepsort(numbers_to_sort_2)
    print(f"Sorted list: {sorted_numbers_2}")

Enter fullscreen mode Exit fullscreen mode

When I run this, it slowly sorts the numbers.

As you can see, it took 13 seconds! Now we are gonna try DIVISION. We will slowly increase the number.

Divided by 100:

The sorting is correct! Now I will add another 100 to it. It is still completely correct and even faster!

I played with the numbers and i found 455 as the breaking point - at 456 it sorted incorrectly. This is gonna differ based on the PC, so this is my specs:

Model: HP ProBook 455 G8
CPU: AMD Ryzen 5 5600U
RAM: 16GB DDR4
i use arch btw

At this point, we cannot get faster with Python, but why stop at Python?

Of course we are gonna be using Rust.

use std::thread;
use std::time::Duration;
use std::sync::{Arc, Mutex};

fn sleepsort(numbers: &[f64]) -> Vec<f64> {
    let sorted_list = Arc::new(Mutex::new(Vec::new()));
    let mut handles = vec![];

    for &num in numbers.iter() {
        let sorted_list_clone = Arc::clone(&sorted_list);

        let handle = thread::spawn(move || {
            thread::sleep(Duration::from_secs_f64(num));

            let mut list = sorted_list_clone.lock().unwrap();

            list.push(num);
        });
        handles.push(handle);
    }

    for handle in handles {
        handle.join().unwrap();
    }

    let final_list = sorted_list.lock().unwrap();

    final_list.clone()
}

fn main() {
    let numbers_to_sort = [5.0, 2.0, 8.0, 1.0, 9.0, 4.0];
    println!("Original list: {:?}", numbers_to_sort);

    let sorted_numbers = sleepsort(&numbers_to_sort);
    println!("Sorted list: {:?}", sorted_numbers);

    let numbers_to_sort_2 = [3.1, 0.5, 4.2, 2.0];
    println!("\nOriginal list: {:?}", numbers_to_sort_2);

    let sorted_numbers_2 = sleepsort(&numbers_to_sort_2);
    println!("Sorted list: {:?}", sorted_numbers_2);
}

Enter fullscreen mode Exit fullscreen mode

This also took 13 seconds to run.

This is divided by 455!

Now I will try dividing by 1000!

Whoa, it just INSTANTLY appeared on my screen!

Now, who said this is the fastest, I will go even further. 5000.

THE SORT IS STILL CORRECT!

Rookie numbers, I will try 10k!

At this point, it sorted incorrectly.

That is not stopping me from finding the EXACT breaking point.

After about 30 more attempts, I found out that Rust handles maximally division by 6760 (on my PC).

This is just the beggining - I will speedit up even MORE in the next article.

Top comments (0)