Today, I am testing sleep-sort. But not just any sleep-sort. I am speeding it up!
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.
For example, we have this list:
list = [1, 3, 2]
This is how it will work:
Now, this is about how it will print:
1
2
3
The way I am speeding it up is this guy.
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}")
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);
}
This also took 13 seconds to run.
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)