Sleep sort: A sorting algorithm without compare

Disclaimer

I'm not inventing this algorithm. I saw a picture of a Javascript version of this algorithm in my feed and love it. So, I try to implement this in Swift. This algorithm is meant to be a joke; don't take it seriously.

You can easily support sarunw.com by checking out this sponsor.

Note Taking:Quickly take note using Voice, Camera, or Typing

Try it for Free

Sorting without compare

Every sorting algorithm I have seen so far have one thing in common, elements that you want to sort have to be comparable. That means if you pick any two elements from an array, it must be a way to tell which comes before. In Swift, we use Comparable protocol.

What if I tell you that there is a sorting algorithm that doesn't require elements in a collection to be comparable.

That's the beauty of this sorting algorithm, an algorithm without compare, Sleep Sort.

Sleep Sort

Here is the implementation of Sleep sort.

extension Array where Element == Int {
    func sleepSorted() -> [Element] {
        var sortedElements = [Element]()
        
        let group = DispatchGroup() // <1>
        
        for element in self { 
            group.enter()
            DispatchQueue.global().async {
                sleep(UInt32(element)) // <2>
                print(element)
                sortedElements.append(element) // <3>
                group.leave()
            }
        }
        
        group.wait() // <4>
        return sortedElements
    }
}

<1> We create a dispatch group because we want to wait for all elements to wake up before continuing execution.
<2> Put each element to sleep.
<3> After wake up, put an element in a sorted array.
<4> After every element are waking up, we return sortedElements

Limitation

It quite fun to think of the limitation of this funny algorithm. I only come up with one limitation so far.

The elements can't be too close together

The difference between each element after convert to time can't be smaller than the operation cost for sleep and asynchronous operation. Let's say the operation cost of each asynchronous operation varies from 0 to 1 second (It needs at most one second between each asynchronous method is one second). The difference can't be smaller than 1.

For example, an array of [0.5, 0.6, 0.7]. The difference between these elements is less than 1.

We want them to sleep at the same time, but because asynchronous operation, which varies from 0 to 1 second, they might not start at the same time and might not wake up immediately.

0.5 start sleep at 0.5 and finish at 1
0.6 start sleep at 0.1 and finish at 0.7
0.7 start sleep at 0.7 and finish at 1.4

So the result is wrong in this case [0.6, 0.5, 0.7]

If the elements are different are larger than 1, this will be fine.

For example, an array of [5, 6.1, 7.2]

5 start sleep at 0.5 and finish at 5.5
6.1 start sleep at 0.1 and finish at 6.2
7.2 start sleep at 0.7 and finish at 7.9

Optimization

We usually measure the performance of an algorithm by Big O Notation, but time complexity measure by Big O Notation is measure relative to the number of input, not the value of the input, so I don't think Big O Notation can apply in this case.

In this case, time complexity would vary on the maximum number of values in an array. We can optimize the runtime by trying to lower these values down.

extension Array where Element == Int {
    func sleepSorted() -> [Element] {
        var sortedElements = [Element]()
        
        let group = DispatchGroup()
        
        for element in self {
            group.enter()
            DispatchQueue.global().async {
                let ms = 1000
                usleep(useconds_t(element * ms))
                print(element)
                sortedElements.append(element)
                group.leave()
            }
        }
        
        group.wait()
        return sortedElements
    }
}

Instead of sleep(), which suspend execution in a second interval, we use usleep, which sleeps in millisecond interval.

usleep() take a parameter of microsecond intervals (1 second equals 1,000,000 microseconds).

Conclusion

I can't tell it is a stupid or genius algorithm, but it sure got a beauty in it. I hope you enjoy the article.

You can easily support sarunw.com by checking out this sponsor.

Note Taking:Quickly take note using Voice, Camera, or Typing

Try it for Free

Related Resources

• Big O notation
• Comparable