Sleep sort: A sorting algorithm without compare

---

Table of Contents

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.

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.

If you want to challenge yourself, try to come up with an implementation of this sorting algorithm.

The clue lies in the name.

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.

Funny exercise; try to come up with your own list and compare it with mine. You can share it with me on Twitter.

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).

You can't reduce the interval down further than a certain number because you will hit with the limitation. Try that and see for yourself.

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.

Related Resources

---

Read more article about Swift, Funny, Sort,

or see all available topic

Feel free to follow me on Twitter and ask your questions related to this post. Thanks for reading and see you next time.

If you enjoy my writing, please check out my Patreon https://www.patreon.com/sarunw and become my supporter. Sharing the article is also greatly appreciated.

Become a patron

Buy me a coffee

Tweet

Share

← Home