Benchmark: javascript count sort vs native sort

Script Preparation code:

var diff = (a, b) => (a - b);
var bigArray = (new Array(1000)).fill(null).map(() => Math.floor(Math.random() * 200));

function countSort(originalArray, smallestElement = undefined, biggestElement = undefined) {
    // Init biggest and smallest elements in array in order to build number bucket array later.
    let detectedSmallestElement = smallestElement || 0;
    let detectedBiggestElement = biggestElement || 0;

    if (smallestElement === undefined || biggestElement === undefined) {
        originalArray.forEach((element) => {
            // Detect biggest element.
            if (element > detectedBiggestElement) {
                detectedBiggestElement = element;
            }

            // Detect smallest element.
            if (element < detectedSmallestElement) {
                detectedSmallestElement = element;
            }
        });
    }

    // Init buckets array.
    // This array will hold frequency of each number from originalArray.
    const buckets = Array(detectedBiggestElement - detectedSmallestElement + 1).fill(0);

    originalArray.forEach((element) => {
        buckets[element - detectedSmallestElement] += 1;
    });

    // Add previous frequencies to the current one for each number in bucket
    // to detect how many numbers less then current one should be standing to
    // the left of current one.
    for (let bucketIndex = 1; bucketIndex < buckets.length; bucketIndex += 1) {
        buckets[bucketIndex] += buckets[bucketIndex - 1];
    }

    // Now let's shift frequencies to the right so that they show correct numbers.
    // I.e. if we won't shift right than the value of buckets[5] will display how many
    // elements less than 5 should be placed to the left of 5 in sorted array
    // INCLUDING 5th. After shifting though this number will not include 5th anymore.
    buckets.pop();
    buckets.unshift(0);

    // Now let's assemble sorted array.
    const sortedArray = Array(originalArray.length).fill(null);
    for (let elementIndex = 0; elementIndex < originalArray.length; elementIndex += 1) {
        // Get the element that we want to put into correct sorted position.
        const element = originalArray[elementIndex];

        // Get correct position of this element in sorted array.
        const elementSortedPosition = buckets[element - detectedSmallestElement];

        // Put element into correct position in sorted array.
        sortedArray[elementSortedPosition] = element;

        // Increase position of current element in the bucket for future correct placements.
        buckets[element - detectedSmallestElement] += 1;
    }

    // Return sorted array.
    return sortedArray;
}

Tests:

count sort
countSort(bigArray)
native sort
bigArray.sort(diff)

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Test case name	Result
count sort
native sort

Fastest: N/A

Slowest: N/A

Latest run results:

Run details: (Test run date: one year ago)

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

Browser/OS: Chrome 131 on Mac OS X 10.15.7

View result in a separate tab

Test name	Executions per second
count sort	166854.2 Ops/sec
native sort	115236.9 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 provided benchmark and its components.

**Benchmark Overview**

The benchmark is designed to compare the performance of two sorting algorithms: JavaScript's native `sort()` method and a custom implementation of "count sort" (also known as counting sort). Count sort is an efficient sorting algorithm that works well for integer arrays with a limited range of values.

**JavaScript Native Sort**

The JavaScript native `sort()` method uses a stable sorting algorithm called Timsort, which is a hybrid of merge sort and insertion sort. Timsort has a worst-case time complexity of O(n log n) and a best-case time complexity of O(n). The native `sort()` method also takes into account the performance characteristics of different browsers and devices.

**Count Sort**

The custom implementation of count sort works by:

1. Detecting the smallest and largest elements in the array to determine the range of values.
2. Creating an array of buckets, where each bucket represents a value in the original array.
3. Counting the frequency of each value in the original array and storing it in the corresponding bucket.
4. Shifting the frequencies to the right to get the correct sorted order.
5. Assembling the sorted array by placing each element at its correct position.

**Comparison**

The benchmark compares the performance of the JavaScript native `sort()` method (Timsort) with the custom implementation of count sort. The comparison is done by executing both algorithms on a large array (`bigArray`) and measuring their execution times.

**Pros and Cons**

* **JavaScript Native Sort:**
	+ Pros:
		- Implemented in the browser, reducing overhead.
		- Has a stable sorting algorithm (Timsort).
		- Handles a wide range of input data types and sizes.
	+ Cons:
		- Can be slower than custom implementations for specific use cases (e.g., integer arrays with a limited range).
* **Count Sort:**
	+ Pros:
		- Optimized for integer arrays with a limited range of values.
		- Can be faster than native `sort()` for certain use cases.
	+ Cons:
		- Requires manual implementation and tuning.
		- Limited applicability to other data types or sizes.

**Other Considerations**

* **Library:** The benchmark uses the `Math` library for mathematical operations, such as random number generation (`Math.random()`).
* **Device Platform:** The benchmark runs on a desktop device (Windows) with Chrome 97 and a 64-bit architecture.
* **Browser:** The benchmark uses the Chrome browser, which may affect performance characteristics.

**Alternatives**

Other sorting algorithms that could be used for comparison in this benchmark include:

1. Quicksort
2. Merge sort
3. Heap sort
4. Radix sort (another counting-based algorithm)

However, it's worth noting that each of these algorithms has its own strengths and weaknesses, and may not be the best choice for every use case.

**Special JS Features/Syntax**

The benchmark does not explicitly use any special JavaScript features or syntax, such as:

1. ES6+ features (e.g., `let`, `const`, arrow functions)
2. Promises
3. Async/Await

However, it's worth noting that some of these features may be used implicitly in the code, such as the use of the `arrow function` (`(a, b) => (a - b)`).

Related benchmarks:

javascript count sort vs native sort (version: 0)

Comparing performance of: count sort vs native sort

Created: 4 years ago by: Registered User

Jump to the latest result

count sort

native sort

Suite status: <idle, ready to run>

Fastest: N/A

Slowest: N/A

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