When I see a post on a similar topic on any social network, there are almost always a lot of comments of this type under it:
Why do you need to know this if there are built-in sorting methods?
Why reinvent the wheel?
It is necessary to pass an interview, objectively there is no need to know it anymore
And I myself used to think the same way until I came to one of the Rostelecom IT teams as a frontend developer. Together we came across a very interesting case: it was necessary to create a widget that could be built into the information systems of all our macro-regional branches and simplify the work of operators in selecting the optimal tariff.
Straight to the point
What do you think will happen after this code is executed? In the meantime, there is no need to know about it. ”
It seems that nothing strange, but there are nuances.
Case number times
We made a problem, technical solution, code, unit tests. The business process is fine too. On surface testing, no problems were found. But when it came to auto tests, the oddities began. The configuration that Node.js 10 was calculating generally gave the correct output, but sometimes the configuration was different. That complicated the process of finding the problem, given that in debug mode, the configuration was always given correct. And some team members reproduced the incorrect configuration, while others did not. And we concluded that there was probably a bug in the old version, and decided to update the version to a newer one.
After a long search for the problem in the code, the error was not found. Testing the project on different Nodes showed that when starting a project on Node, starting with version 11, the answer was always stable. Which was the solution to this problem. Node version was updated to 12 and the problem went away.
Case number two
This time, the configurations were different in different versions of the browser: in Google Chrome 80 the result was correct, but in its 69 version it was not. And then we wondered why the configuration was different.
Saw the versions are different
Opened Google Chrome Release notes
Found that Google Chrome 69 is the last build using V8 6
Opened Release notes V8
And started looking through all the articles between 6 and 7 version V8
After a while, I came across an article Getting things sorted in V8, which says that from 7th version V8 is switching to a stable sorting algorithm TimSort, instead of the previous unstable QuickSort… And then it immediately became clear that there was no magic, and all these bugs were due to unstable sorting.
Sorting in Node.js 10.22 (V8 engine v6.8) QuickSort…
As you can see, the array from the first screenshot has been reordered, although the compare function always returned 0.
Sorting in Node.js 14.5 (V8 engine v7.0) TimSort…
This time, the sort did not change the data anymore.
How to live further
There are several different solutions to suit specific cases. In our case, we decided to use the implementation of the algorithm BlockSort (wikisort)… Yes, the implementation is slower than the browser’s native sort, but now I am confident in the stability of the sorting result where necessary.
Comparison of different solution options with native implementation
We decided to compare:
QuickSort native V8 implementation (node.js 10.22.0)
TimSort native V8 implementation (node.js 14.5.0)
During the test, 10 arrays were created with a random sorted value, each of which contained 100 thousand objects.
In the meantime, there is no need to know about it. ”
From this graph, we can conclude: after the optimizations performed by the V8 engine, sorting WikiSort not inferior to native implementation TimSort, although the difference is quite noticeable during the first sorts. But lodash I would not recommend it.
Where is it stable?
date of release
Explore the technologies you use
Read the official documentation
Keep track of what’s coming in new versions
Do not think that everything has already been done and invented, and you only need to use ready-made solutions