News for hackers. Stuff that matters.

A comment on Visualizing and exploring sorting algorithms in two dimensions.

Re:Visualizing and exploring sorting algorithms in two dimen... by thethirdone on Saturday July 27, 2019 @12:18AM (#20540356)
> 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.

[ Parent | on HN ]
Re:Visualizing and exploring sorting algorithms in two dimen... by thethirdone on Saturday July 27, 2019 @12:39AM (#20540407)
A 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).
[ Parent | on HN ]
Re:Visualizing and exploring sorting algorithms in two dimen... by Leszek on Saturday July 27, 2019 @10:03AM (#20542076)
A more detailed look will show that it uses Timsort:

https://cs.chromium.org/chromium/src/v8/third_party/v8/built...

[ Parent | on HN ]
Re:Visualizing and exploring sorting algorithms in two dimen... by thethirdone on Saturday July 27, 2019 @11:50AM (#20542553)
Well 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.

[ Parent | on HN ]
Re:Visualizing and exploring sorting algorithms in two dimen... by Leszek on Monday July 29, 2019 @08:40AM (#20553938)
Yeah, 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 [1] https://cs.chromium.org/chromium/src/v8/src/builtins/builtin... [2] https://cs.chromium.org/chromium/src/out/Debug/gen/v8/torque... [3] https://cs.chromium.org/chromium/src/v8/src/init/bootstrappe...

[ Parent | on HN ]
Re:Visualizing and exploring sorting algorithms in two dimen... by sorokod on Saturday July 27, 2019 @12:33PM (#20542750)
Java 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.
[ Parent | on HN ]