Run results for: Javascript Sorting Algorithms My Algo Test

Run details:

User agent: Mozilla/5.0 (X11; Linux x86_64; rv:98.0) Gecko/20100101 Firefox/98.0

Browser: Firefox 98

Operating system: Linux

Device Platform: Desktop

Date tested: 2 years ago

Test name	Executions per second
Built-in Sort	11947.8 Ops/sec
Naive Quicksort	1501.8 Ops/sec
Inplace Quicksort	6616.3 Ops/sec
Heap Sort	4411.4 Ops/sec
Merge Sort	2165.5 Ops/sec
Shell Sort	5665.4 Ops/sec
Comb Sort	2546.3 Ops/sec
Insertion Sort	808.0 Ops/sec
Fast QuickSort	6807.6 Ops/sec
mSort	2468.9 Ops/sec
Radix Bucket Sort	2368.4 Ops/sec
Bubble Sort	260.4 Ops/sec
Human Sort	70.8 Ops/sec

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));

Run results for: Javascript Sorting Algorithms My Algo Test

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

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