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

Sponsor sarunw.com and reach thousands of iOS developers.

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

Sponsor sarunw.com and reach thousands of iOS developers.

Read more article about Swift, Funny, Sort, or see all available topic

Every Friday, you'll get a quick recap of all articles and tips posted on this site. No strings attached. Unsubscribe anytime.

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.

Previous
Animation delay and repeatForever in SwiftUI

Explore how delay and repeatForever affect an animation.

Next
Easy way to detect a retain cycle in a view controller

A view controller is one component where memory leak usually takes place since it holds many pieces together. One of the easiest ways to detect them is to see if a view controller is not being deallocated. Let's see how Xcode breakpoint can help you find a leak.

← Home