Benchmark: pure mergeSort - vs - memoized mergeSort

Script Preparation code:

function mergeSort(arr) {
    if (arr.length < 2) {
        return arr;
    }

    const midIndex = Math.floor(arr.length / 2);
    const left = mergeSort(arr.slice(0, midIndex));
    const right = mergeSort(arr.slice(midIndex));
    const result = [];

    while (left.length && right.length) {
        if (left[0] < right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }

    return [...result, ...left, ...right];
}

function memoize(fn) {
    const storage = {};

    return function(...args) {
        const key = JSON.stringify(args);

        if (key in storage) {
            return storage[key];
        } else {
            const result = fn(...args);
            storage[key] = result;
            return result;
        }
    }
}

var memoizedMergeSort = memoize(mergeSort);

var array = [...Array(1000)].map(() => Math.random());

Tests:

pure
[...Array(10)].forEach(() => { mergeSort(array); });
memoized
[...Array(10)].forEach(() => { memoizedMergeSort(array); });

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Test case name	Result
pure
memoized

Fastest: N/A

Slowest: N/A

Latest run results:

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

User agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/126.0.0.0 Safari/537.36

Browser/OS: Chrome 126 on Windows

View result in a separate tab

Test name	Executions per second
pure	86.5 Ops/sec
memoized	671.7 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 benchmark and explain what's being tested, compared, and their pros and cons.

**Benchmark Overview**

The benchmark compares two implementations of the merge sort algorithm:

1. **Pure Merge Sort**: The original implementation without any optimizations or caching.
2. **Memoized Merge Sort**: An optimized version that uses memoization to cache the results of previously computed subarrays.

**Options Compared**

The benchmark tests the performance difference between these two approaches on a large array of 1000 random numbers.

**Pros and Cons**

### Pure Merge Sort

Pros:

* Easy to understand and implement
* No additional memory is required for caching

Cons:

* Without memoization, each recursive call performs redundant computations, leading to exponential time complexity (O(n^2)).

### Memoized Merge Sort

Pros:

* Reduces the time complexity to O(n log n) by caching previously computed subarrays.
* Can lead to significant performance improvements on large datasets.

Cons:

* Requires additional memory for caching the results of previously computed subarrays.
* May introduce additional overhead due to the memoization mechanism.

**Library Used**

In this benchmark, `memoize` is a library function that implements the memoization pattern. It takes a function `fn` as an argument and returns a new function that caches the results of `fn` by storing them in an object `storage`.

The `memoizedMergeSort` variable is created by calling `memoize` with the original `mergeSort` function.

**Special JavaScript Feature**

There's no special JavaScript feature or syntax used in this benchmark. It only utilizes standard JavaScript functions and data structures.

**Other Alternatives**

Other optimization techniques that could be explored for merge sort include:

1. **In-place sorting**: Instead of using a recursive approach, merge sort can be implemented iteratively using an auxiliary array.
2. **Hybrid sorting**: Combining merge sort with other sorting algorithms like insertion sort or quicksort to take advantage of their strengths.
3. **Parallelization**: Using multiple threads or processes to sort the data in parallel, which could lead to significant performance gains on multi-core systems.

These alternatives might not be directly comparable to the memoized approach used in this benchmark, but they represent other ways to optimize merge sort for different use cases and performance characteristics.

Related benchmarks:

pure mergeSort - vs - memoized mergeSort (version: 0)

Comparing performance of: pure vs memoized

Created: one year ago by: Guest

Jump to the latest result

pure

memoized

Suite status: <idle, ready to run>

Fastest: N/A

Slowest: N/A

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