Analyzing Array.sort() & measuring the performance in JavaScript

Ever wondered how does JavaScript sorts the array when you call Array.sort() ?

Well It all depends on the runtime engine of the browser.

for example,

• Chrome uses V8 engine, which is a JavaScript engine written in c++. As per their documentation V8 is Google’s open source high-performance JavaScript and WebAssembly engine, written in C++. It is used in Chrome and in Node.js, among others. It implements ECMAScript and WebAssembly, and runs on Windows 7 or later, macOS 10.12+, and Linux systems that use x64, IA-32, ARM, or MIPS processors. V8 can run standalone, or can be embedded into any C++ application.

• Firefox uses SpiderMonkey engine, which is a JavaScript engine written in C++. As per their documentation SpiderMonkey is Mozilla’s JavaScript and WebAssembly Engine, used in Firefox, Servo and various other projects. It is written in C++, Rust and JavaScript. You can embed it into C++ and Rust projects, and it can be run as a stand-alone shell.

• Safari uses JSC engine, which is a JavaScript engine written in C++. As per their documentation JSC WebKit is the web browser engine used by Safari, Mail, App Store, and many other apps on macOS, iOS, and Linux.

• Microsoft Edge uses Chakra engine, which is a JavaScript engine written in C. As per their documentation ChakraCore is a JavaScript engine with a C API you can use to add support for JavaScript to any C or C compatible project. It can be compiled for x64 processors on Linux macOS and Windows. And x86 and ARM for Windows only. It is a future goal to support x86 and ARM processors on Linux and ARM on macOS.

We will take the 2 most popular browsers as reference, and compare the performance of Array.sort() in each of them.

• Google Chrome

  Since v8 engine Chrome has been using TimSort algorithm for sorting the array.

  

  TimSort developed by Tim Peters in 2002 for python. While Mergesort usually works in recursive fashion, Timsort works iteratively.

  The Array is divided into Run blocks. These runs are sorted using insertion sort one at a time, and they are then combined using the combine function from merge sort. The Array is sorted solely using Insertion Sort if its size is smaller than run block. Depending on the size of the array, the run's size can range from 32 to 64.

Algorithm:

1. Divide the array into the number of blocks known as run.
2. Consider the size of run, either 32 or 64 (32 is the default).
   
3. Sort the individual elements of every run one by one using insertion sort.
4. Merge the sorted runs one by one using the merge function of merge sort.
5. Double the size of merged sub-arrays after every iteration.

WKT the basic operation of insertion sort is Comparing.

When we merge the sorted lists, we come up with a total n-1 comparison because the last element which is left will need to be copied down in the combined list, and there will be no comparison.