3 ms·
> Most languages’ baseline sort operations implement quicksort under the hood, including the standard C library’s gsort() and JavaScript’s Array.prototype.sort(
by thethirdone 7y ago
> Most languages’ baseline sort operations implement quicksort under the hood, including the standard C library’s gsort() and JavaScript’s Array.prototype.sort()
There isn't any "JavaScript's Array.prototype.sort()". Different implementations use different algorithms.
I know V8 used to use Quicksort with insertion sort for (sub)arrays smaller than 10 elements (the implementaion has changed since I last looked, but I don't know what).
But SpiderMonkey has and still does use a bottom up mergesort with insertion sort for subarrays of length 3.
- thethirdone 7y agoA cursory look at the V8 source seems to show that it delegates sorting to std::sort which in libstdc++ (gcc) is Introsort (a hybrid Quicksort + Heapsort).
- Leszek 7y agoA more detailed look will show that it uses Timsort: https://cs.chromium.org/chromium/src/v8/third_party/v8/builtins/array-sort.tq https://cs.chromium.org/chromium/src/v8/third_party/v8/built...
- thethirdone 7y agoWell I don't know how someone not used to the code was suppose to find it at that odd location. Thanks for showing me where its actually implemented.
- Leszek 7y agoYeah, for someone not used to the code it's tough. The "insider knowledge" is that builtins defined in .tq files (files compiled by the Torque compiler[0]) are added to entries in the Builtins enum, which itself is defined as a giant macro[1] that pulls in a Torque generated macro[2]. In the bootstraper (which sets up the standard library), the Builtins::kArrayPrototypeSort builtin is installed as "sort" onto Array.prototype[3], which means you should grep for "ArrayPrototypeSort", which is defined in the linked .tq file. [0] https://v8.dev/docs/torque https://v8.dev/docs/torque [1] https://cs.chromium.org/chromium/src/v8/src/builtins/builtins-definitions.h https://cs.chromium.org/chromium/src/v8/src/builtins/builtin... [2] https://cs.chromium.org/chromium/src/out/Debug/gen/v8/torque-generated/builtin-definitions-tq.h https://cs.chromium.org/chromium/src/out/Debug/gen/v8/torque... [3] https://cs.chromium.org/chromium/src/v8/src/init/bootstrapper.cc?l=1687&rcl=6d7e1dd21b6495d3b55afae266edb65b41c40b20 https://cs.chromium.org/chromium/src/v8/src/init/bootstrappe...
- sorokod 7y agoJava uses Timsort, doc for Arrays.sort: * <p>The implementation was adapted from Tim Peters's list sort for Python * (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt"> * TimSort</a>). It uses techniques from Peter McIlroy's "Optimistic * Sorting and Information Theoretic Complexity", in Proceedings of the * Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474, * January 1993.