HTML Preparation code:
x
 
1
<script>
2
    function swap(ary, a, b) {
3
        var t = ary[a];
4
        ary[a] = ary[b];
5
        ary[b] = t;
6
    }
7
8
    // Built-in with comparison function (default sorting is "dictionary-style")
9
    function builtin_sort(ary) {
10
        return ary.sort(function(a, b) {
11
            return a - b;
12
        });
13
    }
14
15
    // Bubble Sort
16
    function bubble_sort(ary) {
17
        var a, b;
18
        for (a = 0; a < ary.length; a++) {
19
            for (b = a + 1; b < ary.length; b++) {
20
                if (ary[a] > ary[b]) {
21
                    swap(ary, a, b);
22
                }
23
            }
24
        }
25
26
        return ary;
27
    }
28
    //Insertion sort
29
    function insertion_sort(ary) {
30
        for (var i = 1, l = ary.length; i < l; i++) {
31
            var value = ary[i];
32
            for (var j = i - 1; j >= 0; j--) {
33
                if (ary[j] <= value)
34
                    break;
35
                ary[j + 1] = ary[j];
36
            }
37
            ary[j + 1] = value;
38
        }
39
        return ary;
40
    }
41
42
    // Naive (but understandable) quicksort (memory hog)
43
    function naive_quicksort(ary) {
44
        if (ary.length <= 1) {
45
            return ary;
46
        }
47
48
        var less = [],
49
            greater = [],
50
            pivot = ary.pop();
51
52
        for (var i = 0; i < ary.length; i++) {
53
            if (ary[i] < pivot) {
54
                less.push(ary[i]);
55
            } else {
56
                greater.push(ary[i]);
57
            }
58
        }
59
60
        less = naive_quicksort(less);
61
        greater = naive_quicksort(greater);
62
63
        return less.concat(pivot, greater);
64
    }
65
66
    // In place quicksort
67
    function inplace_quicksort_partition(ary, start, end, pivotIndex) {
68
        var i = start,
69
            j = end;
70
        var pivot = ary[pivotIndex];
71
72
        while (true) {
73
            while (ary[i] < pivot) {
74
                i++
75
            };
76
            j--;
77
            while (pivot < ary[j]) {
78
                j--
79
            };
80
            if (!(i < j)) {
81
                return i;
82
            }
83
            swap(ary, i, j);
84
            i++;
85
        }
86
    }
87
88
    function inplace_quicksort(ary, start, end) {
89
        if (start < end - 1) {
90
            var pivotIndex = Math.round((start + end) / 2);
91
92
            pivotIndex = inplace_quicksort_partition(ary, start, end, pivotIndex);
93
94
            inplace_quicksort(ary, start, pivotIndex - 1);
95
            inplace_quicksort(ary, pivotIndex + 1, end);
96
        }
97
98
        return ary;
99
    }
100
101
    // Heap sort
102
    function heapSort(ary) {
103
        heapify(ary);
104
105
        for (var end = ary.length - 1; end > 0; end--) {
106
            swap(ary, end, 0);
107
            shiftDown(ary, 0, end - 1);
108
        }
109
110
        return ary;
111
    }
112
113
    function heapify(ary) {
114
        for (var start = (ary.length >> 1) - 1; start >= 0; start--) {
115
            shiftDown(ary, start, ary.length - 1);
116
        }
117
    }
118
119
    function shiftDown(ary, start, end) {
120
        var root = start,
121
            child, s;
122
123
        while (root * 2 + 1 <= end) {
124
            child = root * 2 + 1;
125
            s = root;
126
127
            if (ary[s] < ary[child]) {
128
                s = child;
129
            }
130
131
            if (child + 1 <= end && ary[s] < ary[child + 1]) {
132
                s = child + 1;
133
            }
134
135
            if (s !== root) {
136
                swap(ary, root, s);
137
                root = s;
138
            } else {
139
                return;
140
            }
141
        }
142
    }
143
144
    // Merge sort
145
    function merge_sort(ary) {
146
        if (ary.length <= 1) {
147
            return ary;
148
        }
149
150
        var m = ary.length >> 1;
151
152
        var left = ary.slice(0, m),
153
            right = ary.slice(m);
154
155
        return merge(merge_sort(left), merge_sort(right));
156
    }
157
158
    function merge(left, right) {
159
        var result = [],
160
            li = 0,
161
            ri = 0;
162
163
        while (li < left.length || ri < right.length) {
164
            if (li < left.length && ri < right.length) {
165
                if (left[li] <= right[ri]) {
166
                    result.push(left[li]);
167
                    li++;
168
                } else {
169
                    result.push(right[ri]);
170
                    ri++;
171
                }
172
            } else if (li < left.length) {
173
                result.push(left[li]);
174
                li++;
175
            } else if (ri < right.length) {
176
                result.push(right[ri]);
177
                ri++;
178
            }
179
        }
180
181
        return result;
182
    }
183
184
    // Shell sort
185
    function shell_sort(ary) {
186
        var inc = Math.round(ary.length / 2),
187
            i, j, t;
188
189
        while (inc > 0) {
190
            for (i = inc; i < ary.length; i++) {
191
                t = ary[i];
192
                j = i;
193
                while (j >= inc && ary[j - inc] > t) {
194
                    ary[j] = ary[j - inc];
195
                    j -= inc;
196
                }
197
                ary[j] = t;
198
            }
199
            inc = Math.round(inc / 2.2);
200
        }
201
202
        return ary;
203
    }
204
    //Comb Sort (Basically bubblesort with a small modification, but heaps faster)
205
    function comb_sort(ary) {
206
        var gap = ary.length;
207
        while (true) {
208
            gap = newgap(gap);
209
            var swapped = false;
210
            for (var i = 0, l = ary.length; i < l; i++) {
211
                var j = i + gap;
212
                if (ary[i] < ary[j]) {
213
                    swap(ary, i, j);
214
                    swapped = true;
215
                }
216
            }
217
            if (gap == 1 && !swapped)
218
                break;
219
        }
220
        return ary;
221
    }
222
223
    function newgap(gap) {
224
        gap = ((gap * 10) / 13) | 0;
225
        if (gap == 9 || gap == 10)
226
            gap = 11;
227
        if (gap < 1)
228
            gap = 1;
229
        return gap;
230
    }
231
    //faster quicksort using a stack to eliminate recursion, sorting inplace to reduce memory usage, and using insertion sort for small partition sizes
232
    function fast_quicksort(ary) {
233
        var stack = [];
234
        var entry = [0, ary.length, 2 * Math.floor(Math.log(ary.length) / Math.log(2))];
235
        stack.push(entry);
236
        while (stack.length > 0) {
237
            entry = stack.pop();
238
            var start = entry[0];
239
            var end = entry[1];
240
            var depth = entry[2];
241
            if (depth == 0) {
242
                ary = shell_sort_bound(ary, start, end);
243
                continue;
244
            }
245
            depth--;
246
            var pivot = Math.round((start + end) / 2);
247
248
            var pivotNewIndex = inplace_quicksort_partition(ary, start, end, pivot);
249
            if (end - pivotNewIndex > 16) {
250
                entry = [pivotNewIndex, end, depth];
251
                stack.push(entry);
252
            }
253
            if (pivotNewIndex - start > 16) {
254
                entry = [start, pivotNewIndex, depth];
255
                stack.push(entry);
256
            }
257
        }
258
        ary = insertion_sort(ary);
259
        return ary;
260
    }
261
262
    function shell_sort_bound(ary, start, end) {
263
        var inc = Math.round((start + end) / 2),
264
            i, j, t;
265
266
        while (inc >= start) {
267
            for (i = inc; i < end; i++) {
268
                t = ary[i];
269
                j = i;
270
                while (j >= inc && ary[j - inc] > t) {
271
                    ary[j] = ary[j - inc];
272
                    j -= inc;
273
                }
274
                ary[j] = t;
275
            }
276
            inc = Math.round(inc / 2.2);
277
        }
278
279
        return ary;
280
    }
281
282
    function mSort(list) {
283
        if (list.length < 14) {
284
            return insertion_sort(list);
285
        }
286
287
        var half = Math.floor(list.length / 2);
288
        var a = mSort(list.slice(0, half));
289
        var b = mSort(list.slice(half, list.length));
290
        var aCount = 0;
291
        var bCount = 0;
292
        var returnList = [];
293
294
        while (true) {
295
            if (a[aCount] <= b[bCount]) {
296
                returnList.push(a[aCount]);
297
                aCount++;
298
                if (aCount === a.length) {
299
                    returnList = returnList.concat(b.slice(bCount, b.length));
300
                    break;
301
                }
302
            } else {
303
                returnList.push(b[bCount]);
304
                bCount++;
305
                if (bCount === b.length) {
306
                    returnList = returnList.concat(a.slice(aCount, a.length));
307
                    break;
308
                }
309
            }
310
        }
311
        return returnList;
312
    }
313
314
    function bubbleSort(items) {
315
        var length = items.length;
316
        for (var i = 0; i < length; i++) { //Number of passes
317
            for (var j = 0; j < (length - i - 1); j++) { //Notice that j < (length - i)
318
                //Compare the adjacent positions
319
                if (items[j] > items[j + 1]) {
320
                    //Swap the numbers
321
                    var tmp = items[j]; //Temporary variable to hold the current number
322
                    items[j] = items[j + 1]; //Replace current number with adjacent number
323
                    items[j + 1] = tmp; //Replace adjacent number with current number
324
                }
325
            }
326
        }
327
    }
328
329
    https: //stackoverflow.com/a/38979903/8769328
330
        function radixBucketSort(arr) {
331
            var idx1, idx2, idx3, len1, len2, radix, radixKey;
332
            var radices = {},
333
                buckets = {},
334
                num, curr;
335
            var currLen, radixStr, currBucket;
336
337
            len1 = arr.length;
338
            len2 = 10; // radix sort uses ten buckets
339
340
            // find the relevant radices to process for efficiency        
341
            for (idx1 = 0; idx1 < len1; idx1++) {
342
                radices[arr[idx1].toString().length] = 0;
343
            }
344
345
            // loop for each radix. For each radix we put all the items
346
            // in buckets, and then pull them out of the buckets.
347
            for (radix in radices) {
348
                // put each array item in a bucket based on its radix value
349
                len1 = arr.length;
350
                for (idx1 = 0; idx1 < len1; idx1++) {
351
                    curr = arr[idx1];
352
                    // item length is used to find its current radix value
353
                    currLen = curr.toString().length;
354
                    // only put the item in a radix bucket if the item
355
                    // key is as long as the radix
356
                    if (currLen >= radix) {
357
                        // radix starts from beginning of key, so need to
358
                        // adjust to get redix values from start of stringified key
359
                        radixKey = curr.toString()[currLen - radix];
360
                        // create the bucket if it does not already exist
361
                        if (!buckets.hasOwnProperty(radixKey)) {
362
                            buckets[radixKey] = [];
363
                        }
364
                        // put the array value in the bucket
365
                        buckets[radixKey].push(curr);
366
                    } else {
367
                        if (!buckets.hasOwnProperty('0')) {
368
                            buckets['0'] = [];
369
                        }
370
                        buckets['0'].push(curr);
371
                    }
372
                }
373
                // for current radix, items are in buckets, now put them
374
                // back in the array based on their buckets
375
                // this index moves us through the array as we insert items
376
                idx1 = 0;
377
                // go through all the buckets
378
                for (idx2 = 0; idx2 < len2; idx2++) {
379
                    // only process buckets with items
380
                    if (buckets[idx2] != null) {
381
                        currBucket = buckets[idx2];
382
                        // insert all bucket items into array
383
                        len1 = currBucket.length;
384
                        for (idx3 = 0; idx3 < len1; idx3++) {
385
                            arr[idx1++] = currBucket[idx3];
386
                        }
387
                    }
388
                }
389
                buckets = {};
390
            }
391
        }
392
393
    function humanSort(arr) {
394
        const len = arr.length;
395
        for (let i = 0; i < len; i++) {
396
            let subIndex = i;
397
            while (arr[subIndex] > arr[subIndex + 1] && subIndex > -1) {
398
                const curr = arr[subIndex];
399
                arr[subIndex] = arr[subIndex + 1];
400
                arr[subIndex + 1] = curr;
401
                subIndex--;
402
            }
403
        }
404
        return arr;
405
    }
406
</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

Experimental features:

  • 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: 3 years ago)
Mozilla/5.0 (X11; Linux x86_64; rv:98.0) Gecko/20100101 Firefox/98.0
Firefox 98 on Linux
View result in a separate tab
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