Sleep Sort

Jul 17, 2026Pranav-0440

EditReport

Definition

Sleep Sort is an esoteric and humorous sorting algorithm that relies on concurrency and time delays. The algorithm works by creating a separate thread or asynchronous task for each element in the input array. Each thread sleeps for a duration proportional to the value of its corresponding element, then appends/prints the element.

Because of the sleep delays, smaller numbers wake up and are output first, resulting in a sorted sequence.

---

Characteristics

• Concurrency-Based:
  • Sleep Sort cannot be executed sequentially; it requires multithreading or asynchronous event loops to schedule sleep operations in parallel.
• Esoteric & Humorous:
  • It is not a practical sorting algorithm and is used primarily as a meme or to demonstrate basic concurrency concepts.
• Hardware & OS Dependent:
  • The correctness of the output is heavily dependent on scheduler precision and CPU load. Under high CPU loads or with very close numbers, threads might wake up out of order, leading to incorrect sorting.

---

Complexity Analysis

• Time Complexity:
  • Worst Case: $\mathcal{O}(n + \text{max\_val})$ — The time complexity depends not only on the number of elements $n$ but also on the magnitude of the largest value in the array.
  • Average Case: $\mathcal{O}(n + \text{max\_val})$
  • Best Case: $\mathcal{O}(n + \text{max\_val})$
• Space Complexity: $\mathcal{O}(n)$ — Extra memory is needed to spawn $n$ threads, timers, or queue structures.

---

Implementations

Here are the concurrency-based implementations of Sleep Sort in various programming languages:

C++ Implementation

#include <iostream>
#include <vector>
#include <thread>
#include <chrono>
#include <mutex>

using namespace std;

mutex mtx;
vector<int> sortedArr;

// Thread function for sleep sort
void sleepAndAdd(int val) {
    // Sleep for a duration proportional to the value
    this_thread::sleep_for(chrono::milliseconds(val * 10)); // scaled to 10ms per unit
    
    lock_guard<mutex> lock(mtx);
    sortedArr.push_back(val);
}

void sleepSort(const vector<int>& arr) {
    vector<thread> threads;
    
    // Spawn a thread for each element
    for (int x : arr) {
        threads.push_back(thread(sleepAndAdd, x));
    }
    
    // Wait for all threads to finish
    for (auto& t : threads) {
        t.join();
    }
}

int main() {
    vector<int> arr = {4, 7, 2, 9, 1, 5, 3};
    
    cout << "Original array: ";
    for (int x : arr) cout << x << " ";
    cout << endl;

    sleepSort(arr);

    cout << "Sorted array: ";
    for (int x : sortedArr) cout << x << " ";
    cout << endl;

    return 0;
}

Python Implementation

import threading
import time

sorted_arr = []
lock = threading.Lock()

def sleep_and_append(val):
    # Sleep for duration proportional to the value (scaled by 0.01 seconds)
    time.sleep(val * 0.01)
    with lock:
        sorted_arr.append(val)

def sleep_sort(arr):
    threads = []
    for x in arr:
        t = threading.Thread(target=sleep_and_append, args=(x,))
        threads.append(t)
        t.start()
        
    for t in threads:
        t.join()

if __name__ == "__main__":
    arr = [4, 7, 2, 9, 1, 5, 3]
    print("Original array:", arr)
    sleep_sort(arr)
    print("Sorted array:", sorted_arr)

Java Implementation

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class SleepSort {
    public static void sleepSort(int[] arr) {
        List<Integer> sortedList = Collections.synchronizedList(new ArrayList<>());
        List<Thread> threads = new ArrayList<>();

        for (int x : arr) {
            Thread t = new Thread(() -> {
                try {
                    // Sleep duration proportional to the value
                    Thread.sleep(x * 10L); // 10ms scale
                    sortedList.add(x);
                } catch (InterruptedException e) {
                    Thread.currentThread().interrupt();
                }
            });
            threads.add(t);
            t.start();
        }

        // Wait for all threads to complete
        for (Thread t : threads) {
            try {
                t.join();
            } catch (InterruptedException e) {
                Thread.currentThread().interrupt();
            }
        }

        // Print sorted result
        System.out.println("Sorted array: " + sortedList);
    }

    public static void main(String[] args) {
        int[] arr = {4, 7, 2, 9, 1, 5, 3};
        sleepSort(arr);
    }
}

JavaScript Implementation

async function sleepSort(arr) {
    const sortedArr = [];
    
    // Helper function to sleep
    const sleep = (ms) => new Promise(resolve => setTimeout(resolve, ms));
    
    // Create promises for each element
    const promises = arr.map(async (x) => {
        await sleep(x * 10); // scale of 10ms
        sortedArr.push(x);
    });
    
    // Wait for all promises to resolve
    await Promise.all(promises);
    return sortedArr;
}

const arr = [4, 7, 2, 9, 1, 5, 3];
sleepSort(arr).then(sorted => {
    console.log("Sorted array:", sorted);
});

C Implementation

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <unistd.h>

#define SCALE_FACTOR 10000 // 10 milliseconds in microseconds

pthread_mutex_t lock;
int* sorted_arr;
int write_idx = 0;

// Thread function
void* sleepAndWrite(void* arg) {
    int val = *(int*)arg;
    free(arg); // Free dynamic memory allocated for thread arg

    // Sleep for val * SCALE_FACTOR microseconds
    usleep(val * SCALE_FACTOR);

    pthread_mutex_lock(&lock);
    sorted_arr[write_idx++] = val;
    pthread_mutex_unlock(&lock);

    return NULL;
}

void sleepSort(int arr[], int n) {
    pthread_t* threads = (pthread_t*)malloc(n * sizeof(pthread_t));
    sorted_arr = (int*)malloc(n * sizeof(int));
    pthread_mutex_init(&lock, NULL);

    for (int i = 0; i < n; i++) {
        int* arg = (int*)malloc(sizeof(int));
        *arg = arr[i];
        pthread_create(&threads[i], NULL, sleepAndWrite, arg);
    }

    for (int i = 0; i < n; i++) {
        pthread_join(threads[i], NULL);
    }

    // Copy sorted values back to original array
    for (int i = 0; i < n; i++) {
        arr[i] = sorted_arr[i];
    }

    pthread_mutex_destroy(&lock);
    free(threads);
    free(sorted_arr);
}

int main() {
    int arr[] = {4, 7, 2, 9, 1, 5, 3};
    int n = sizeof(arr) / sizeof(arr[0]);

    sleepSort(arr, n);

    printf("Sorted array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

---

Common Issues and Pitfalls

1. Precision & Thread Race Conditions: If elements are very close (e.g., [1, 1]) or the sleep interval is too short, scheduling delays may cause out-of-order execution, leading to incorrect sort results.
2. Negative Integers: Sleep Sort cannot naturally handle negative integers, as sleeping for negative durations is not supported.
3. Extremely Large Numbers: If the array contains a large value (e.g., 100000), the program will hang and take a long time to finish executing just for that one element.