A little while ago, I saw a post on X about a new sorting algorithm they created. It was a simple algorithm that promised to only iterate through the array once. Intrigued, I looked at the code and it was maybe the best code I've ever seen.
async function setTimeoutSort(arr: number[]): Promise<number[]> {
const sortedArray: number[] = []
const promises = arr.map(num => {
return new Promise<void>((resolve) => {
setTimeout(() => {
sortedArray.push(num)
resolve()
}, num)
})
})
await Promise.all(promises)
return sortedArray
}Basically it will set a timer for each number in an array where the time is the value of the number itself. Once the timer is up, the number will be added to the sorted array. And it will do this for each number in the array. Because bigger numbers will take longer, they will be added to the sorted array later than the smaller numbers. It's a terrible sorting algorithm if you have more than a few numbers in the array or if the numbers are too big. Buy hey, it works!
The Honeymoon Phase
I presented this algorithm to my team and they were in disbelief that it actually worked. My boss, ever the critic, began to question the validity of the algorithm and explore its time complexity. I proposed that the algorithm was O(n) because it only iterated through the array once. After some back and forth and some boring nuanced conversations, we began to explore how this algorithm behaved when the array was BIG.
How would this algorithm behave if the array was millions of elements long? Is it possible that the first few timers would finish before the the last timers are even started? I needed to do some research into the node event loop to figure out how this would behave.
The Node Event Loop
In construction...