Benchmark: Count sort vs JS native sort

HTML Preparation code:

<div id=''></div>

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) => {
            // Visit element.
            this.callbacks.visitingCallback(element);

            // Detect biggest element.
            if (this.comparator.greaterThan(element, detectedBiggestElement)) {
                detectedBiggestElement = element;
            }

            // Detect smallest element.
            if (this.comparator.lessThan(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) => {
        // Visit element.
        this.callbacks.visitingCallback(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];

        // Visit element.
        this.callbacks.visitingCallback(element);

        // 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
bigArray.sort(diff)

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Test case name	Result
count sort
Native

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/130.0.0.0 Safari/537.36

Browser/OS: Chrome 130 on Mac OS X 10.15.7

View result in a separate tab

Test name	Executions per second
count sort	0.0 Ops/sec
Native	49185.2 Ops/sec

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

LLMs can make mistakes. Check important info.

I'll break down the provided benchmark definition, options compared, and considerations for the count sort algorithm in JavaScript.

**Benchmark Definition:**

The benchmark is designed to compare two sorting algorithms: Count Sort and JavaScript's native built-in sorting algorithm (used by the `sort()` method).

**Options Compared:**

1. **Count Sort:** This is a counting-based sorting algorithm that works well with integer data types, particularly when the range of values is small compared to the number of elements.
2. **JavaScript Native Sorting Algorithm:** This is implemented in JavaScript and uses various algorithms like Timsort (for most modern browsers) or Merge Sort (in older versions). It's a general-purpose sorting algorithm that works well with a wide range of data types.

**Pros and Cons:**

1. **Count Sort:**
	* Pros:
		+ Efficient for integer data types, especially when the range is small.
		+ Can be implemented in-place, reducing memory usage.
	* Cons:
		+ Only suitable for integer data types.
		+ Limited to handling small ranges (typically up to 32 bits).
2. **JavaScript Native Sorting Algorithm:**
	* Pros:
		+ General-purpose and works well with a wide range of data types.
		+ Optimized for performance in modern browsers.
	* Cons:
		+ Can be slower than specialized algorithms like Count Sort for integer data types.
		+ May not perform as well on smaller arrays.

**Other Considerations:**

1. **Library Usage:** The benchmark uses a custom `countSort` function that implements the Count Sort algorithm. This is necessary because JavaScript's native sorting algorithm does not support custom sorting behaviors.
2. **Special JS Feature/ Syntax:** There are no special JavaScript features or syntax used in this benchmark.

**Alternatives:**

1. **Merge Sort:** Another popular sorting algorithm that can be implemented in JavaScript.
2. **Heap Sort:** A comparison-based sorting algorithm that is relatively efficient and easy to implement.
3. **Radix Sort:** A non-comparison sorting algorithm that works well for integer data types with a fixed number of digits.

To improve the benchmark, you could consider adding more test cases to cover different scenarios, such as:

* Larger arrays
* Floating-point numbers
* Non-integer data types (e.g., strings)
* Edge cases (e.g., empty arrays, arrays with only one element)

Additionally, you can explore using a more robust testing framework to ensure the benchmark is reliable and accurate.

Related benchmarks:

Count sort vs JS native sort (version: 0)

Comparing performance of: count sort vs Native

Created: 4 years ago by: Guest

Jump to the latest result

count sort

Native

Suite status: <idle, ready to run>

Fastest: N/A

Slowest: N/A

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