Benchmark: Javascript Sorting Algorithms

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 = {};
    }
  }
</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));

Historical Performance Data aggregated from 269 community runs

Desktop Results:

Chrome 183 runs

Fast QuickSort

75K/s

Inplace Quicksort

58K/s

Heap Sort

30K/s

mSort

18K/s

Comb Sort

14K/s

Shell Sort

14K/s

Merge Sort

11K/s

Radix Bucket Sort

9K/s

Built-in Sort

9K/s

Naive Quicksort

5K/s

Insertion Sort

4K/s

Bubble Sort

823/s

Fastest: Fast QuickSort (91.4x faster)

View exact numbers

✓ Fast QuickSort: 75,176 ops/sec
• Inplace Quicksort: 58,378 ops/sec
• Heap Sort: 30,411 ops/sec
• mSort: 17,640 ops/sec
• Comb Sort: 14,439 ops/sec
• Shell Sort: 14,358 ops/sec
• Merge Sort: 10,621 ops/sec
• Radix Bucket Sort : 8,994 ops/sec
• Built-in Sort: 8,716 ops/sec
• Naive Quicksort: 5,286 ops/sec
• Insertion Sort: 4,027 ops/sec
• Bubble Sort: 823 ops/sec

Firefox 45 runs

Built-in Sort

27K/s

Shell Sort

10K/s

Fast QuickSort

10K/s

Inplace Quicksort

10K/s

mSort

7K/s

Radix Bucket Sort

5K/s

Heap Sort

5K/s

Merge Sort

5K/s

Naive Quicksort

5K/s

Comb Sort

4K/s

Insertion Sort

2K/s

Bubble Sort

514/s

Fastest: Built-in Sort (52.1x faster)

View exact numbers

✓ Built-in Sort: 26,754 ops/sec
• Shell Sort: 10,227 ops/sec
• Fast QuickSort: 9,932 ops/sec
• Inplace Quicksort: 9,770 ops/sec
• mSort: 7,366 ops/sec
• Radix Bucket Sort : 5,266 ops/sec
• Heap Sort: 5,100 ops/sec
• Merge Sort: 4,837 ops/sec
• Naive Quicksort: 4,780 ops/sec
• Comb Sort: 3,883 ops/sec
• Insertion Sort: 1,767 ops/sec
• Bubble Sort: 514 ops/sec

Other 7 runs

Fast QuickSort

9K/s

Inplace Quicksort

7K/s

Heap Sort

4K/s

Shell Sort

3K/s

Comb Sort

2K/s

mSort

2K/s

Merge Sort

1K/s

Built-in Sort

1K/s

Radix Bucket Sort

782/s

Insertion Sort

482/s

Naive Quicksort

466/s

Bubble Sort

197/s

Fastest: Fast QuickSort (46.7x faster)

View exact numbers

✓ Fast QuickSort: 9,199 ops/sec
• Inplace Quicksort: 7,084 ops/sec
• Heap Sort: 4,382 ops/sec
• Shell Sort: 2,957 ops/sec
• Comb Sort: 2,246 ops/sec
• mSort: 2,021 ops/sec
• Merge Sort: 1,181 ops/sec
• Built-in Sort: 1,081 ops/sec
• Radix Bucket Sort : 782 ops/sec
• Insertion Sort: 482 ops/sec
• Naive Quicksort: 466 ops/sec
• Bubble Sort: 197 ops/sec

Mobile Results:

Chrome 22 runs

Fast QuickSort

33K/s

Inplace Quicksort

25K/s

Heap Sort

16K/s

Shell Sort

10K/s

Comb Sort

9K/s

mSort

9K/s

Merge Sort

6K/s

Radix Bucket Sort

5K/s

Built-in Sort

4K/s

Naive Quicksort

3K/s

Insertion Sort

2K/s

Bubble Sort

753/s

Fastest: Fast QuickSort (44.2x faster)

View exact numbers

✓ Fast QuickSort: 33,267 ops/sec
• Inplace Quicksort: 24,756 ops/sec
• Heap Sort: 16,345 ops/sec
• Shell Sort: 10,216 ops/sec
• Comb Sort: 9,440 ops/sec
• mSort: 8,773 ops/sec
• Merge Sort: 5,634 ops/sec
• Radix Bucket Sort : 4,513 ops/sec
• Built-in Sort: 4,493 ops/sec
• Naive Quicksort: 2,822 ops/sec
• Insertion Sort: 2,373 ops/sec
• Bubble Sort: 753 ops/sec

Safari 12 runs

Inplace Quicksort

93K/s

Fast QuickSort

81K/s

Shell Sort

32K/s

Heap Sort

24K/s

Built-in Sort

18K/s

Comb Sort

17K/s

mSort

14K/s

Merge Sort

10K/s

Naive Quicksort

8K/s

Insertion Sort

6K/s

Radix Bucket Sort

3K/s

Bubble Sort

2K/s

Fastest: Inplace Quicksort (51.5x faster)

View exact numbers

✓ Inplace Quicksort: 92,725 ops/sec
• Fast QuickSort: 80,658 ops/sec
• Shell Sort: 31,859 ops/sec
• Heap Sort: 24,391 ops/sec
• Built-in Sort: 17,797 ops/sec
• Comb Sort: 17,411 ops/sec
• mSort: 13,860 ops/sec
• Merge Sort: 10,040 ops/sec
• Naive Quicksort: 8,240 ops/sec
• Insertion Sort: 5,859 ops/sec
• Radix Bucket Sort : 2,534 ops/sec
• Bubble Sort: 1,801 ops/sec

Results show median performance across all community submissions. Run this benchmark yourself to verify on your device.

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

Fastest: N/A

Slowest: N/A

Latest run results:

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

User agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:151.0) Gecko/20100101 Firefox/151.0

Browser/OS: Firefox 151 on Mac OS X 10.15

View result in a separate tab

Built-in Sort

109K/s

Fast QuickSort

53K/s

Inplace Quicksort

52K/s

Shell Sort

37K/s

Heap Sort

32K/s

mSort

29K/s

Merge Sort

18K/s

Naive Quicksort

16K/s

Comb Sort

11K/s

Radix Bucket Sort

11K/s

Insertion Sort

4K/s

Bubble Sort

1K/s

View exact numbers

Test name	Executions per second
✓ Built-in Sort	109,205 Ops/sec
Fast QuickSort	53,492 Ops/sec
Inplace Quicksort	52,448 Ops/sec
Shell Sort	37,493 Ops/sec
Heap Sort	31,828 Ops/sec
mSort	29,071 Ops/sec
Merge Sort	18,352 Ops/sec
Naive Quicksort	15,757 Ops/sec
Comb Sort	11,081 Ops/sec
Radix Bucket Sort	10,775 Ops/sec
Insertion Sort	4,098 Ops/sec
Bubble Sort	1,373 Ops/sec

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

LLMs can make mistakes. Check important info.

It appears you've provided a JSON string containing data from browser performance tests. I'll extract the relevant information and provide a concise answer.

**Summary of Browser Performance Tests:**

Here are the results:

1. **Shell Sort**: 17190.72265625 executions per second
2. **Fast QuickSort**: 16542.87109375 executions per second
3. **mSort**: 15878.294921875 executions per second
4. **Radix Bucket Sort**: 9717.962890625 executions per second
5. **Naive Quicksort**: 8607.0185546875 executions per second
6. **Merge Sort**: 8061.673828125 executions per second
7. **Heap Sort**: 7147.79541015625 executions per second
8. **Comb Sort**: 6608.69580078125 executions per second
9. **Insertion Sort**: 3091.8203125 executions per second
10. **Bubble Sort**: 978.94677734375 executions per second

**Fastest Algorithm:**

The fastest algorithm is **Shell Sort**, with an execution rate of approximately 17,191 executions per second.

Let me know if you'd like to analyze anything else from the data!

Javascript Sorting Algorithms (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`

Created: 8 years ago by: Registered User

Go to the latest 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

Historical Performance Data aggregated from 269 community runs

Desktop Results:

Chrome 183 runs

Firefox 45 runs

Other 7 runs

Mobile Results:

Chrome 22 runs

Safari 12 runs

Suite status: <idle, ready to run>

Fastest: N/A

Slowest: N/A

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

Javascript Sorting Algorithms (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

Created: 8 years ago by: Registered User

Go to the latest 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

Historical Performance Data aggregated from 269 community runs

Desktop Results:

Chrome 183 runs

Firefox 45 runs

Other 7 runs

Mobile Results:

Chrome 22 runs

Safari 12 runs

Suite status: <idle, ready to run>

Fastest: N/A

Slowest: N/A

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

Related benchmarks

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`