What hides Array # sort: reverse engineering by improvised means
As you may know, the JavaScript language specification does not prescribe any particular implementation of the sort method on arrays. The algorithm that is “under the hood” may differ (and differs) in different browsers. Theoretically, you can imagine a situation where the performance of your web application depends on how exactly the sorting of arrays is implemented in a particular engine.
If we are talking about an open source browser, then you can simply open this code and see what algorithm is used there. However, there are closed-source browsers (we will not point with a finger). What to do in this case?
Since we are at Habré, I’m ready to assume that some readers are already reaching out for their favorite disassemblers, while some others are preparing to call their friends from one small and weak company. However, today we will not delve into machine code or use insider information. We will look funny pictures.
It is possible to learn something about the implementation of the sort method right inside the script. It consists in the fact that this method takes as an argument a comparator - a function of two variables that returns a numeric value, based on which the sorting algorithm concludes which of the arguments is greater. This allows you to sort arrays of arbitrary objects, not just numbers or strings. Also, which is important in our case, it allows us to know exactly which elements of the array and in what order the sort method compares with each other. For example:
')
However, it is not enough to get the data, you need to figure out how to interpret them. When I last visited the bookstore, there was no book called “Classification of sorting algorithms based on what elements they compare to each other, for teapots”. Perhaps it has since appeared there, but I decided to do without it and rely on a person’s ability to recognize visual patterns.
We will do this: take a certain array, then sort it using a specially trained comparator, which saves data about each comparison. Then we take this data and construct the following diagram based on them: for each comparison, in which the elements with indices a and b took part (meaning the indices of these elements in an already sorted array), we mark the point with coordinates (a, b). At the same time, we mark a point with coordinates (b, a) so that it is beautiful and that the form of the diagram does not depend on the fine details of the implementation. And the point will not be simple, but colored: its color will symbolize when this comparison took place. Comparisons that happened at the very beginning of sorting, we note in red, those that are closer to the end - blue, and between them there will be other colors of the rainbow.
Oddly enough, this plan was not so stupid. I implemented several of the most common algorithms, and they really gave clearly distinguishable patterns. Here, for example, selection sorting:
And this is what bubble sort looks like. The difference is well discernible, and, in principle, it is not difficult to understand where it comes from.
Both are inefficient sorting algorithms (average time complexity - O (n 2 )). More advanced algorithms use fewer comparisons, so the diagram is less colored. At the beginning of the article there is a diagram for pyramidal sorting (heap sort), there are much more white pixels on it.
Each sort has its own recognizable pattern. Smooth gradient in sorting by selection, gradient with small transverse stripes in bubble sorting, stripes of different colors in sorting inserts (insertion sort). Quick sorting (quicksort) crosses everything with crosses, sorting with a binary tree (tree sort) with similar crosses, but not monotone, but variegated ones. Merge sort has characteristic short blue stripes closer to the diagonal. A pyramid sorting diagram resembles a merge sort, but has a pronounced color gradient.
“However, what about browsers?” An inquisitive reader will ask me, who has not forgotten how the article began. Especially for such readers, I made a page where you can see the Array # sort diagram in your current browser and compare it with the diagrams of some well-known algorithms.
In short:
“However, what about Internet Explorer?” An inquisitive reader will ask me. Well, I knew that it would sometime come to this question ... With IE, there was an embarrassment. Diagrams obtained in IE11 and Edge do not coincide with any of the implemented algorithms. They look something like this:
There is something in common with sorting AVL-tree, but there is no clear match. However, I do not lose hope, and I continue to add new algorithms to my page. And if your hands are itching to help me, I will gladly accept your pull requests.
At the moment this is all I have to say. I hope you were interested.
Upd: as suggested by Viacheslav01 , in IE11 and Edge for arrays of small size, modified sorting inserts are used; he added the implementation of this sorting to the page so that everyone could check and make sure. For arrays larger than 512 elements, quick sorting is used, which again can be seen by adding "? Size = 10" to the URL.
Upd2: Using black magic, it was found that IE7 uses pyramidal sorting. This result is not yet available for verification by the general public due to the fact that IE7 does not support canvas, and I have not yet written down a fallback.
Hidden text
I doubt very much that this can happen in practice, but as a person who wrote a certain number of term papers and dissertations at one time, I simply could not do without the section “Use in the national economy”.
If we are talking about an open source browser, then you can simply open this code and see what algorithm is used there. However, there are closed-source browsers (we will not point with a finger). What to do in this case?
Since we are at Habré, I’m ready to assume that some readers are already reaching out for their favorite disassemblers, while some others are preparing to call their friends from one small and weak company. However, today we will not delve into machine code or use insider information. We will look funny pictures.
It is possible to learn something about the implementation of the sort method right inside the script. It consists in the fact that this method takes as an argument a comparator - a function of two variables that returns a numeric value, based on which the sorting algorithm concludes which of the arguments is greater. This allows you to sort arrays of arbitrary objects, not just numbers or strings. Also, which is important in our case, it allows us to know exactly which elements of the array and in what order the sort method compares with each other. For example:
')
function compare(a, b){ console.log(a, b); return a - b; } However, it is not enough to get the data, you need to figure out how to interpret them. When I last visited the bookstore, there was no book called “Classification of sorting algorithms based on what elements they compare to each other, for teapots”. Perhaps it has since appeared there, but I decided to do without it and rely on a person’s ability to recognize visual patterns.
We will do this: take a certain array, then sort it using a specially trained comparator, which saves data about each comparison. Then we take this data and construct the following diagram based on them: for each comparison, in which the elements with indices a and b took part (meaning the indices of these elements in an already sorted array), we mark the point with coordinates (a, b). At the same time, we mark a point with coordinates (b, a) so that it is beautiful and that the form of the diagram does not depend on the fine details of the implementation. And the point will not be simple, but colored: its color will symbolize when this comparison took place. Comparisons that happened at the very beginning of sorting, we note in red, those that are closer to the end - blue, and between them there will be other colors of the rainbow.
Oddly enough, this plan was not so stupid. I implemented several of the most common algorithms, and they really gave clearly distinguishable patterns. Here, for example, selection sorting:
And this is what bubble sort looks like. The difference is well discernible, and, in principle, it is not difficult to understand where it comes from.
Both are inefficient sorting algorithms (average time complexity - O (n 2 )). More advanced algorithms use fewer comparisons, so the diagram is less colored. At the beginning of the article there is a diagram for pyramidal sorting (heap sort), there are much more white pixels on it.
Each sort has its own recognizable pattern. Smooth gradient in sorting by selection, gradient with small transverse stripes in bubble sorting, stripes of different colors in sorting inserts (insertion sort). Quick sorting (quicksort) crosses everything with crosses, sorting with a binary tree (tree sort) with similar crosses, but not monotone, but variegated ones. Merge sort has characteristic short blue stripes closer to the diagonal. A pyramid sorting diagram resembles a merge sort, but has a pronounced color gradient.
“However, what about browsers?” An inquisitive reader will ask me, who has not forgotten how the article began. Especially for such readers, I made a page where you can see the Array # sort diagram in your current browser and compare it with the diagrams of some well-known algorithms.
In short:
- Fresh Firefox uses merge sort, but on fairly small arrays it switches to something resembling sorting inserts. You can check it yourself by adding "? Size = 4" pages to the URL (without quotes, of course).
- Fresh Chrome Desktop uses quick sort. However, on iOS it uses merge sort.
- Safari on MacOS and iOS also uses merge sort.
- Yandex.Browser uses merge sort.
- And the old Opera uses merge sort.
- Konqueror and rekonq use sorting by a binary tree, red-black or similar.
“However, what about Internet Explorer?” An inquisitive reader will ask me. Well, I knew that it would sometime come to this question ... With IE, there was an embarrassment. Diagrams obtained in IE11 and Edge do not coincide with any of the implemented algorithms. They look something like this:
There is something in common with sorting AVL-tree, but there is no clear match. However, I do not lose hope, and I continue to add new algorithms to my page. And if your hands are itching to help me, I will gladly accept your pull requests.
At the moment this is all I have to say. I hope you were interested.
Upd: as suggested by Viacheslav01 , in IE11 and Edge for arrays of small size, modified sorting inserts are used; he added the implementation of this sorting to the page so that everyone could check and make sure. For arrays larger than 512 elements, quick sorting is used, which again can be seen by adding "? Size = 10" to the URL.
Upd2: Using black magic, it was found that IE7 uses pyramidal sorting. This result is not yet available for verification by the general public due to the fact that IE7 does not support canvas, and I have not yet written down a fallback.
Source: https://habr.com/ru/post/303748/
All Articles