Author: Casual @ edamame front end

background

I happened to see a funny sort in the tech group. At first glance, this sorting algorithm is funny, but the funny sorting algorithm gives the correct sorting result. It makes you want to know more about how it works.

The Event Loop is introduced

We know that JavaScript is single-threaded, that when the program is running, only one thread exists. A single threaded JavaScript executes section by section, the first one executed, and then the next one executed. However, if you encounter a task that takes a long time, such as interface requests and I/O operations, waiting for subsequent tasks will not only waste resources, but also cause the page to freeze and the interaction will be poor. To solve this problem, JavaScript divides tasks into synchronous and asynchronous tasks for different processing.

JavaScript executes synchronous tasks in the execution context stack in order on the main thread. The first task is executed before the second task is executed. Instead of stopping and waiting for an asynchronous task, it suspends and continues to execute the synchronous task in the current stack. When an asynchronous task returns a result, the result is added to the task queue. Usually, the task queue stores the callback function after the asynchronous task is completed.

When the execution stack completes, the free main thread reads whether there are any tasks in the task queue. If so, the main thread will add the first task in the task queue to the execution stack. After the execution of the task in the execution stack is completed, the main thread will query the task in the task queue and read the task in the execution stack to execute. This is called an Event Loop.

There is a widely circulated chart on the Internet that summarizes the process:

Sort code analysis

OK, with all that said, we finally see the keyword associated with the sorting algorithm: setTimeout. As an asynchronous task, the callback function is added to the task queue each time it iterates through the array based on the current value, filling the new array with data. Due to the difference in size of values, small values with short delay time will be added to the task queue first. Finally, the purpose of sorting is achieved by using the time difference of Event Loop.

Regardless of the delay, if you look at the code, it’s just a loop through the whole sort, the sort code is order n in time. And from the current example: in the sorting process, data of the same size will not change the order before and after sorting, which is a stable sorting algorithm. We can even encapsulate this code and modify it to get the sorted array with a callback:

function eventLoopSort(list, callback) {
  var newList = [];
  var sum = 0;
  list.forEach(item= > {
    setTimeout((a)= > {
      newList.push(item);
    }, item * 100)
    sum += item;
  });
  setTimeout((a)= > {
    callback && callback(newList);
  }, sum * 100);
}

var list = [1.1.4.6.2.3.9.8.7];
eventLoopSort(list, data => {
  console.log(data) // [1, 1, 2, 3, 4, 6, 7, 8, 9]
})
Copy the code

The problem summary

With all this seriousness, it still doesn’t change the fact that this sort is a spoof and can’t be applied to real code. In addition to the long setTimeout delay, this sort can still be wrong when dealing with large amounts of data. Considering that the code itself takes time to execute, when faced with a large amount of data, the previous data takes a long time to execute, long enough to offset the delay, the sorting will be completely wrong.

Finally, whoever wrote this “joke” code for the first time knows a lot about how browsers work. This is what I want to express through this article, and I hope it will help you with your learning through this spoof, fun format.