Benchmark: Javascript Sorting Algorithms My Algo Test

Javascript Sorting Algorithms My Algo Test (version: 0)

Port from jsperf(https://jsperf.com/sorting-algorithms/58)

Comparing performance of: `Built-in Sort vs Naive Quicksort vs Inplace Quicksort vs Heap Sort vs Merge Sort vs Shell Sort vs Comb Sort vs Insertion Sort vs Fast QuickSort vs mSort vs Radix Bucket Sort vs Bubble Sort vs Human Sort`

Created: 5 years ago by: Guest

Go to the latest result

HTML Preparation code:

<script>
    function swap(ary, a, b) {
        var t = ary[a];
        ary[a] = ary[b];
        ary[b] = t;
    }

    // Built-in with comparison function (default sorting is "dictionary-style")
    function builtin_sort(ary) {
        return ary.sort(function(a, b) {
            return a - b;
        });
    }

    // Bubble Sort
    function bubble_sort(ary) {
        var a, b;
        for (a = 0; a < ary.length; a++) {
            for (b = a + 1; b < ary.length; b++) {
                if (ary[a] > ary[b]) {
                    swap(ary, a, b);
                }
            }
        }

        return ary;
    }
    //Insertion sort
    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;
    }

    // Naive (but understandable) quicksort (memory hog)
    function naive_quicksort(ary) {
        if (ary.length <= 1) {
            return ary;
        }

        var less = [],
            greater = [],
            pivot = ary.pop();

        for (var i = 0; i < ary.length; i++) {
            if (ary[i] < pivot) {
                less.push(ary[i]);
            } else {
                greater.push(ary[i]);
            }
        }

        less = naive_quicksort(less);
        greater = naive_quicksort(greater);

        return less.concat(pivot, greater);
    }

    // In place quicksort
    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 inplace_quicksort(ary, start, end) {
        if (start < end - 1) {
            var pivotIndex = Math.round((start + end) / 2);

            pivotIndex = inplace_quicksort_partition(ary, start, end, pivotIndex);

            inplace_quicksort(ary, start, pivotIndex - 1);
            inplace_quicksort(ary, pivotIndex + 1, end);
        }

        return ary;
    }

    // Heap sort
    function heapSort(ary) {
        heapify(ary);

        for (var end = ary.length - 1; end > 0; end--) {
            swap(ary, end, 0);
            shiftDown(ary, 0, end - 1);
        }

        return ary;
    }

    function heapify(ary) {
        for (var start = (ary.length >> 1) - 1; start >= 0; start--) {
            shiftDown(ary, start, ary.length - 1);
        }
    }

    function shiftDown(ary, start, end) {
        var root = start,
            child, s;

        while (root * 2 + 1 <= end) {
            child = root * 2 + 1;
            s = root;

            if (ary[s] < ary[child]) {
                s = child;
            }

            if (child + 1 <= end && ary[s] < ary[child + 1]) {
                s = child + 1;
            }

            if (s !== root) {
                swap(ary, root, s);
                root = s;
            } else {
                return;
            }
        }
    }

    // Merge sort
    function merge_sort(ary) {
        if (ary.length <= 1) {
            return ary;
        }

        var m = ary.length >> 1;

        var left = ary.slice(0, m),
            right = ary.slice(m);

        return merge(merge_sort(left), merge_sort(right));
    }

    function merge(left, right) {
        var result = [],
            li = 0,
            ri = 0;

        while (li < left.length || ri < right.length) {
            if (li < left.length && ri < right.length) {
                if (left[li] <= right[ri]) {
                    result.push(left[li]);
                    li++;
                } else {
                    result.push(right[ri]);
                    ri++;
                }
            } else if (li < left.length) {
                result.push(left[li]);
                li++;
            } else if (ri < right.length) {
                result.push(right[ri]);
                ri++;
            }
        }

        return result;
    }

    // Shell sort
    function shell_sort(ary) {
        var inc = Math.round(ary.length / 2),
            i, j, t;

        while (inc > 0) {
            for (i = inc; i < ary.length; 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;
    }
    //Comb Sort (Basically bubblesort with a small modification, but heaps faster)
    function comb_sort(ary) {
        var gap = ary.length;
        while (true) {
            gap = newgap(gap);
            var swapped = false;
            for (var i = 0, l = ary.length; i < l; i++) {
                var j = i + gap;
                if (ary[i] < ary[j]) {
                    swap(ary, i, j);
                    swapped = true;
                }
            }
            if (gap == 1 && !swapped)
                break;
        }
        return ary;
    }

    function newgap(gap) {
        gap = ((gap * 10) / 13) | 0;
        if (gap == 9 || gap == 10)
            gap = 11;
        if (gap < 1)
            gap = 1;
        return gap;
    }
    //faster quicksort using a stack to eliminate recursion, sorting inplace to reduce memory usage, and using insertion sort for small partition sizes
    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 mSort(list) {
        if (list.length < 14) {
            return insertion_sort(list);
        }

        var half = Math.floor(list.length / 2);
        var a = mSort(list.slice(0, half));
        var b = mSort(list.slice(half, list.length));
        var aCount = 0;
        var bCount = 0;
        var returnList = [];

        while (true) {
            if (a[aCount] <= b[bCount]) {
                returnList.push(a[aCount]);
                aCount++;
                if (aCount === a.length) {
                    returnList = returnList.concat(b.slice(bCount, b.length));
                    break;
                }
            } else {
                returnList.push(b[bCount]);
                bCount++;
                if (bCount === b.length) {
                    returnList = returnList.concat(a.slice(aCount, a.length));
                    break;
                }
            }
        }
        return returnList;
    }

    function bubbleSort(items) {
        var length = items.length;
        for (var i = 0; i < length; i++) { //Number of passes
            for (var j = 0; j < (length - i - 1); j++) { //Notice that j < (length - i)
                //Compare the adjacent positions
                if (items[j] > items[j + 1]) {
                    //Swap the numbers
                    var tmp = items[j]; //Temporary variable to hold the current number
                    items[j] = items[j + 1]; //Replace current number with adjacent number
                    items[j + 1] = tmp; //Replace adjacent number with current number
                }
            }
        }
    }

    https: //stackoverflow.com/a/38979903/8769328
        function radixBucketSort(arr) {
            var idx1, idx2, idx3, len1, len2, radix, radixKey;
            var radices = {},
                buckets = {},
                num, curr;
            var currLen, radixStr, currBucket;

            len1 = arr.length;
            len2 = 10; // radix sort uses ten buckets

            // find the relevant radices to process for efficiency        
            for (idx1 = 0; idx1 < len1; idx1++) {
                radices[arr[idx1].toString().length] = 0;
            }

            // loop for each radix. For each radix we put all the items
            // in buckets, and then pull them out of the buckets.
            for (radix in radices) {
                // put each array item in a bucket based on its radix value
                len1 = arr.length;
                for (idx1 = 0; idx1 < len1; idx1++) {
                    curr = arr[idx1];
                    // item length is used to find its current radix value
                    currLen = curr.toString().length;
                    // only put the item in a radix bucket if the item
                    // key is as long as the radix
                    if (currLen >= radix) {
                        // radix starts from beginning of key, so need to
                        // adjust to get redix values from start of stringified key
                        radixKey = curr.toString()[currLen - radix];
                        // create the bucket if it does not already exist
                        if (!buckets.hasOwnProperty(radixKey)) {
                            buckets[radixKey] = [];
                        }
                        // put the array value in the bucket
                        buckets[radixKey].push(curr);
                    } else {
                        if (!buckets.hasOwnProperty('0')) {
                            buckets['0'] = [];
                        }
                        buckets['0'].push(curr);
                    }
                }
                // for current radix, items are in buckets, now put them
                // back in the array based on their buckets
                // this index moves us through the array as we insert items
                idx1 = 0;
                // go through all the buckets
                for (idx2 = 0; idx2 < len2; idx2++) {
                    // only process buckets with items
                    if (buckets[idx2] != null) {
                        currBucket = buckets[idx2];
                        // insert all bucket items into array
                        len1 = currBucket.length;
                        for (idx3 = 0; idx3 < len1; idx3++) {
                            arr[idx1++] = currBucket[idx3];
                        }
                    }
                }
                buckets = {};
            }
        }

    function humanSort(arr) {
        const len = arr.length;
        for (let i = 0; i < len; i++) {
            let subIndex = i;
            while (arr[subIndex] > arr[subIndex + 1] && subIndex > -1) {
                const curr = arr[subIndex];
                arr[subIndex] = arr[subIndex + 1];
                arr[subIndex + 1] = curr;
                subIndex--;
            }
        }
        return arr;
    }
</script>

Script Preparation code:

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

Tests:

Built-in Sort
builtin_sort(input.slice(0));
Naive Quicksort
naive_quicksort(input.slice(0));
Inplace Quicksort
inplace_quicksort(input.slice(0), 0, input.length);
Heap Sort
heapSort(input.slice(0));
Merge Sort
merge_sort(input.slice(0));
Shell Sort
shell_sort(input.slice(0));
Comb Sort
comb_sort(input.slice(0));
Insertion Sort
insertion_sort(input.slice(0));
Fast QuickSort
fast_quicksort(input.slice(0));
mSort
mSort(input.slice(0));
Radix Bucket Sort
radixBucketSort(input.slice(0))
Bubble Sort
bubbleSort(input.slice(0));
Human Sort
humanSort(input.slice(0));

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Test case name	Result
Built-in Sort
Naive Quicksort
Inplace Quicksort
Heap Sort
Merge Sort
Shell Sort
Comb Sort
Insertion Sort
Fast QuickSort
mSort
Radix Bucket Sort
Bubble Sort
Human Sort

Fastest: N/A

Slowest: N/A

Latest run results:

Run details: (Test run date: 10 months ago)

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

Browser/OS: Chrome 140 on Windows

View result in a separate tab

Fast QuickSort

85K/s

Inplace Quicksort

63K/s

Heap Sort

45K/s

Shell Sort

20K/s

mSort

16K/s

Comb Sort

13K/s

Merge Sort

11K/s

Built-in Sort

8K/s

Radix Bucket Sort

8K/s

Naive Quicksort

5K/s

Insertion Sort

5K/s

Bubble Sort

2K/s

Human Sort

642/s

View exact numbers

Test name	Executions per second
✓ Fast QuickSort	85,499 Ops/sec
Inplace Quicksort	62,911 Ops/sec
Heap Sort	45,471 Ops/sec
Shell Sort	20,483 Ops/sec
mSort	16,363 Ops/sec
Comb Sort	13,073 Ops/sec
Merge Sort	11,155 Ops/sec
Built-in Sort	8,250 Ops/sec
Radix Bucket Sort	8,063 Ops/sec
Naive Quicksort	4,838 Ops/sec
Insertion Sort	4,663 Ops/sec
Bubble Sort	1,563 Ops/sec
Human Sort	642 Ops/sec

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

LLMs can make mistakes. Check important info.

It seems like you're ready to dive into the data!

Since I don't see any explicit questions or prompts in your message, I'll assume you'd like me to analyze and extract insights from the provided data. If you could provide more context or specific questions about the data, I'd be happy to help.

Assuming there's no question, here are some observations I can make:

1. **Browser and OS distribution**: The most common browser is Firefox 98, with a significant presence of Linux operating systems.
2. **Sort algorithms**: The most frequently executed sort algorithms on these devices are Heap Sort, Shell Sort, Merge Sort, Naive Quicksort, Insertion Sort, Bubble Sort, and Human Sort (which might not be a standard sorting algorithm).
3. **Execution rates**: There's a wide range of execution rates for each algorithm, indicating that some users prefer faster sorting algorithms while others prioritize other factors.

Please provide more context or ask specific questions about the data if you'd like me to dig deeper!