Benchmark: array sort - MeasureThat.net

Script Preparation code:

var input = [];
for (var i = 0; i < 1000; i++) {
  input[i] = Math.round(Math.random() * 1000000);
}

Tests:

built in sort
input.slice(0).sort(function(a, b) { return a - b; });
custom sort
function fast_quicksort(ary) { var stack = []; var entry = [0, ary.length, 2 * Math.floor(Math.log(ary.length) / Math.log(2))]; stack.push(entry); while (stack.length > 0) { entry = stack.pop(); var start = entry[0]; var end = entry[1]; var depth = entry[2]; if (depth == 0) { ary = shell_sort_bound(ary, start, end); continue; } depth--; var pivot = Math.round((start + end) / 2); var pivotNewIndex = inplace_quicksort_partition(ary, start, end, pivot); if (end - pivotNewIndex > 16) { entry = [pivotNewIndex, end, depth]; stack.push(entry); } if (pivotNewIndex - start > 16) { entry = [start, pivotNewIndex, depth]; stack.push(entry); } } ary = insertion_sort(ary); return ary; } function shell_sort_bound(ary, start, end) { var inc = Math.round((start + end) / 2), i, j, t; while (inc >= start) { for (i = inc; i < end; i++) { t = ary[i]; j = i; while (j >= inc && ary[j - inc] > t) { ary[j] = ary[j - inc]; j -= inc; } ary[j] = t; } inc = Math.round(inc / 2.2); } return ary; } function inplace_quicksort_partition(ary, start, end, pivotIndex) { var i = start, j = end; var pivot = ary[pivotIndex]; while(true) { while(ary[i] < pivot) {i++}; j--; while(pivot < ary[j]) {j--}; if(!(i<j)) { return i; } swap(ary,i,j); i++; } } function insertion_sort(ary) { for(var i=1,l=ary.length;i<l;i++) { var value = ary[i]; for(var j=i - 1;j>=0;j--) { if(ary[j] <= value) break; ary[j+1] = ary[j]; } ary[j+1] = value; } return ary; } function swap(ary, a, b) { var t = ary[a]; ary[a] = ary[b]; ary[b] = t; } fast_quicksort(input.slice(0));

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Test case name	Result
built in sort
custom sort

Fastest: N/A

Slowest: N/A

Latest run results:

Run details: (Test run date: 2 years ago)

User agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_7) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/120.0.0.0 Safari/537.36

Browser/OS: Chrome 120 on Mac OS X 10.15.7

View result in a separate tab

Test name	Executions per second
built in sort	3823.6 Ops/sec
custom sort	13533.8 Ops/sec

Autogenerated LLM Summary (model llama3.2:3b, generated one year ago):

LLMs can make mistakes. Check important info.

Let's break down the benchmark and explain what's being tested, compared, and their pros and cons.

**Benchmark Definition**

The benchmark is defined by two test cases:

1. **Built-in Sort**: The built-in `sort()` function is used to sort an array of random integers. This is a standard JavaScript method that sorts an array in ascending order.
2. **Custom Sort**: A custom sorting algorithm, implemented as the `fast_quicksort` function, is used to sort the same array.

**What's being tested?**

Both test cases measure the execution time of the sorting algorithms on an array of 1000 random integers.

**Options Compared**

The two options compared are:

1. **Built-in Sort**: The built-in JavaScript `sort()` function.
2. **Custom Sort**: A custom implementation of the quicksort algorithm, implemented as the `fast_quicksort` function.

**Pros and Cons**

**Built-in Sort (JavaScript sort())**

Pros:

* Easy to implement and use
* Well-tested and optimized by Mozilla/Google
* Fast for small to medium-sized arrays

Cons:

* Not designed for large datasets or performance-critical applications
* May not be suitable for specific data types (e.g., integers, strings)

**Custom Sort (Fast Quicksort)**

Pros:

* Can be highly optimized for specific use cases and hardware architectures
* Allows for more control over the sorting process
* May perform better for large datasets or performance-critical applications

Cons:

* More complex to implement and maintain than built-in sort
* Requires manual management of memory and data structures (e.g., pivot selection, partitioning)

**Library: Shell Sort**

In the custom sort test case, a `shell_sort_bound` function is used as part of the quicksort algorithm. Shell sort is a comparison-based sorting algorithm that uses a combination of insertion sort and merge sort.

Pros:

* Stable and efficient for certain data types (e.g., integers)
* Can be implemented more efficiently than quicksort

Cons:

* Less widely supported than quicksort
* May not perform as well on larger datasets or more complex data structures

**Special JS Feature: ES6+**

Note that the custom sort implementation uses features introduced in ECMAScript 2015 (ES6), such as arrow functions, template literals, and destructuring. These features are now widely supported by modern browsers.

**Other Alternatives**

Other sorting algorithms that could be used instead of built-in sort or custom quicksort include:

* Merge sort
* Heap sort
* Radix sort (for large datasets of integers)
* Timsort (a hybrid sorting algorithm that combines elements of merge sort and insertion sort)

These alternatives may offer trade-offs in terms of performance, complexity, and memory usage.

In summary, the benchmark tests two competing sorting algorithms: built-in JavaScript `sort()` and a custom implementation of quicksort. The results highlight the importance of choosing an optimized sorting algorithm for specific use cases and hardware architectures.

Related benchmarks:

array sort (version: 0)

Comparing performance of: built in sort vs custom sort

Created: 2 years ago by: Guest

Jump to the latest result

built in sort

custom sort

Suite status: <idle, ready to run>

Fastest: N/A

Slowest: N/A

Autogenerated LLM Summary (model llama3.2:3b, generated one year ago):