Benchmark: Javascript Sorting Algorithms test1

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);
}
var sorted = builtin_sort(input.slice(0));
input2 = input.slice(0).map(e => e + '')
var sorted2 = builtin_sort(input2.slice(0));

Tests:

Built-in Sort
builtin_sort(input.slice(0));
pre sorted
builtin_sort(sorted.slice(0));
builtin_sort(input2.slice(0));
builtin_sort(input2.slice(0));
builtin_sort(sorted2.slice(0));
builtin_sort(sorted2.slice(0));

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Test case name	Result
Built-in Sort
pre sorted
builtin_sort(input2.slice(0));
builtin_sort(sorted2.slice(0));

Fastest: N/A

Slowest: N/A

Latest run results:

Run details: (Test run date: 2 years ago)

User agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_7) AppleWebKit/605.1.15 (KHTML, like Gecko) Version/17.4.1 Safari/605.1.15

Browser/OS: Safari 17 on Mac OS X 10.15.7

View result in a separate tab

Test name	Executions per second
Built-in Sort	16670.1 Ops/sec
pre sorted	29487.1 Ops/sec
builtin_sort(input2.slice(0));	2779.0 Ops/sec
builtin_sort(sorted2.slice(0));	5977.3 Ops/sec

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

LLMs can make mistakes. Check important info.

I'll provide the answer after analyzing the provided code snippet and test cases.

**Code Analysis:**

The provided JavaScript code is an implementation of Radix Sort, which is a non-comparative sorting algorithm that sorts numbers digit by digit from least significant to most. The code uses a bucketing approach to sort the input array.

Here's a high-level overview of the code:

1. Initialize an empty object `buckets` to store sorted elements.
2. Iterate through each character in the key ( radix ) and create buckets for each value.
3. Insert elements from the input array into their corresponding buckets based on the current radix.
4. Rebuild the sorted array by inserting elements from each bucket.

**Test Cases Analysis:**

The provided test cases are designed to evaluate the performance of Radix Sort:

1. `builtin_sort(input.slice(0))`: Tests built-in sorting algorithm on an input array.
2. `builtin_sort(sorted.slice(0))`: Tests built-in sorting algorithm on a pre-sorted array.
3. `builtin_sort(input2.slice(0))`: Tests Radix Sort implementation on the same input as test case 1.
4. `builtin_sort(sorted2.slice(0))`: Tests Radix Sort implementation on a pre-sorted array, similar to test case 2.

**Benchmark Results Analysis:**

The latest benchmark results show that:

* The built-in sorting algorithm performs better than Radix Sort for some test cases (e.g., `pre sorted` and `builtin_sort(sorted2.slice(0))`).
* Radix Sort performs reasonably well for other test cases, such as `built-in Sort` and `builtin_sort(input2.slice(0))`.

**Conclusion:**

Based on the provided code, test cases, and benchmark results, it appears that:

* The built-in sorting algorithm is generally faster than Radix Sort.
* Radix Sort is still a viable option for certain use cases, such as when dealing with large datasets or numbers with multiple digits.

However, without more context or information about the specific requirements and constraints of the project, it's difficult to provide a definitive recommendation on which algorithm to choose.

Related benchmarks:

Javascript Sorting Algorithms test1 (version: 0)

Comparing performance of: Built-in Sort vs pre sorted vs builtin_sort(input2.slice(0)); vs builtin_sort(sorted2.slice(0));

Created: 2 years ago by: Guest

Jump to the latest result

Built-in Sort

pre sorted

builtin_sort(input2.slice(0));

builtin_sort(sorted2.slice(0));

Suite status: <idle, ready to run>

Fastest: N/A

Slowest: N/A

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