Benchmark: Javascript Sorting Algorithms 3.0

Javascript Sorting Algorithms 3.0 (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 Iterative quick sort

Created: one year ago by: Guest

Jump to the latest result

HTML Preparation code:

<script>
  
  function quickSortHelper(arrayInput, left, right) {
  let i = left;
  let j = right;
  let pivotPoint = arrayInput[Math.round((left + right) * .5)];

  // Loop
  while (i <= j) {

    while (arrayInput[i] < pivotPoint) {
      i++;
    }

    while (arrayInput[j] > pivotPoint) {
      j--;
    }

    if (i <= j) {
      let tempStore = arrayInput[i];

      arrayInput[i] = arrayInput[j];
      i++;

      arrayInput[j] = tempStore;
      j--;
    }

  }

  // Swap
  if (left < j) {
    quickSortHelper(arrayInput, left, j);
  }

  if (i < right) {
    quickSortHelper(arrayInput, i, right);
  }

  return arrayInput;
}

function quickSort(input) {
  return quickSortHelper(input, 0, input.length - 1);
}
                
                
  // Javascript program for implementation of QuickSort
      
    /* This function takes last element as pivot,
    places the pivot element at its correct
    position in sorted array, and places all
    smaller (smaller than pivot) to left of
    pivot and all greater elements to right
    of pivot */
    function partition(arr, low, high)
    {
        let temp;
        let pivot = arr[high];
   
        // index of smaller element
        let i = (low - 1);
        for (let j = low; j <= high - 1; j++) {
            // If current element is smaller
            // than or equal to pivot
            if (arr[j] <= pivot) {
                i++;
   
                // swap arr[i] and arr[j]
                temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
   
        // swap arr[i+1] and arr[high]
        // (or pivot)
   
        temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;
   
        return i + 1;
    }
   
    /* A[] --> Array to be sorted,
    l --> Starting index,
    h --> Ending index */
    function quickSortIterative(arr, l, h)
    {
        // Create an auxiliary stack
        let stack = new Array(h - l + 1);
        stack.fill(0);
   
        // initialize top of stack
        let top = -1;
   
        // push initial values of l and h to
        // stack
        stack[++top] = l;
        stack[++top] = h;
   
        // Keep popping from stack while
        // is not empty
        while (top >= 0) {
            // Pop h and l
            h = stack[top--];
            l = stack[top--];
   
            // Set pivot element at its
            // correct position in
            // sorted array
            let p = partition(arr, l, h);
   
            // If there are elements on
            // left side of pivot, then
            // push left side to stack
            if (p - 1 > l) {
                stack[++top] = l;
                stack[++top] = p - 1;
            }
   
            // If there are elements on
            // right side of pivot, then
            // push right side to stack
            if (p + 1 < h) {
                stack[++top] = p + 1;
                stack[++top] = h;
            }
        }
    }
      
    
    
  
    
    
  
  
  
// This code is contributed by mukesh07.
  
  
  
  
  
  
  
  
  
  
  
  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
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));
Iterative quick sort
quickSortIterative(input.slice(0), 0, input.length-1);

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
Iterative quick sort

Fastest: N/A

Slowest: N/A

Latest run results:

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

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

Browser/OS: Chrome 117 on Windows

View result in a separate tab

Test name	Executions per second
Built-in Sort	7650.0 Ops/sec
Naive Quicksort	28830.7 Ops/sec
Inplace Quicksort	54013.5 Ops/sec
Heap Sort	26623.3 Ops/sec
Merge Sort	9663.4 Ops/sec
Shell Sort	13800.8 Ops/sec
Comb Sort	15104.9 Ops/sec
Insertion Sort	3709.3 Ops/sec
Fast QuickSort	57603.8 Ops/sec
mSort	14115.3 Ops/sec
Radix Bucket Sort	7337.0 Ops/sec
Bubble Sort	651.3 Ops/sec
Iterative quick sort	48241.3 Ops/sec

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

LLMs can make mistakes. Check important info.

Please provide the data in a format that I can work with, such as a Python dictionary or a JSON object.

However, based on the format you provided, it appears to be a JSON array of dictionaries, where each dictionary represents a test result. Here is an example of how you could parse this data in Python:
```
import json

data = '''
[
    {
        "RawUAString": "Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/117.0.0.0 Safari/537.36",
        "Browser": "Chrome 117",
        "DevicePlatform": "Desktop",
        "OperatingSystem": "Windows",
        "ExecutionsPerSecond": 28830.74609375,
        "TestName": "Naive Quicksort"
    },
    {
        "RawUAString": "Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/117.0.0.0 Safari/537.36",
        "Browser": "Chrome 117",
        "DevicePlatform": "Desktop",
        "OperatingSystem": "Windows",
        "ExecutionsPerSecond": 26623.265625,
        "TestName": "Heap Sort"
    },
    {
        "RawUAString": "Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/117.0.0.0 Safari/537.36",
        "Browser": "Chrome 117",
        "DevicePlatform": "Desktop",
        "OperatingSystem": "Windows",
        "ExecutionsPerSecond": 15104.853515625,
        "TestName": "Comb Sort"
    },
    {
        "RawUAString": "Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/117.0.0.0 Safari/537.36",
        "Browser": "Chrome 117",
        "DevicePlatform": "Desktop",
        "OperatingSystem": "Windows",
        "ExecutionsPerSecond": 14115.2763671875,
        "TestName": "mSort"
    },
    {
        "RawUAString": "Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/117.0.0.0 Safari/537.36",
        "Browser": "Chrome 117",
        "DevicePlatform": "Desktop",
        "OperatingSystem": "Windows",
        "ExecutionsPerSecond": 13800.84375,
        "TestName": "Shell Sort"
    },
    {
        "RawUAString": "Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/117.0.0.0 Safari/537.36",
        "Browser": "Chrome 117",
        "DevicePlatform": "Desktop",
        "OperatingSystem": "Windows",
        "ExecutionsPerSecond": 9663.3662109375,
        "TestName": "Merge Sort"
    },
    {
        "RawUAString": "Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/117.0.0.0 Safari/537.36",
        "Browser": "Chrome 117",
        "DevicePlatform": "Desktop",
        "OperatingSystem": "Windows",
        "ExecutionsPerSecond": 7650.01806640625,
        "TestName": "Built-in Sort"
    },
    {
        "RawUAString": "Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/117.0.0.0 Safari/537.36",
        "Browser": "Chrome 117",
        "DevicePlatform": "Desktop",
        "OperatingSystem": "Windows",
        "ExecutionsPerSecond": 7337.00048828125,
        "TestName": "Radix Bucket Sort "
    },
    {
        "RawUAString": "Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/117.0.0.0 Safari/537.36",
        "Browser": "Chrome 117",
        "DevicePlatform": "Desktop",
        "OperatingSystem": "Windows",
        "ExecutionsPerSecond": 3709.265625,
        "TestName": "Insertion Sort"
    },
    {
        "RawUAString": "Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/117.0.0.0 Safari/537.36",
        "Browser": "Chrome 117",
        "DevicePlatform": "Desktop",
        "OperatingSystem": "Windows",
        "ExecutionsPerSecond": 3211.2890625,
        "TestName": "Bubble Sort"
    },
    {
        "RawUAString": "Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/117.0.0.0 Safari/537.36",
        "Browser": "Chrome 117",
        "DevicePlatform": "Desktop",
        "OperatingSystem": "Windows",
        "ExecutionsPerSecond": 2822.265625,
        "TestName": "Selection Sort"
    }
]

# Parse the JSON data
data_dict = json.loads(data)

# Print the test names and their corresponding executions per second
for result in data_dict:
    print(f"Test Name: {result['TestName']}, Executions Per Second: {result['ExecutionsPerSecond']}")
```
This will output the following:
```
Test Name: Naive Quicksort, Executions Per Second: 28830.74609375
Test Name: Heap Sort, Executions Per Second: 26623.265625
Test Name: Comb Sort, Executions Per Second: 15104.853515625
Test Name: mSort, Executions Per Second: 14115.2763671875
Test Name: Shell Sort, Executions Per Second: 13800.84375
Test Name: Merge Sort, Executions Per Second: 9663.3662109375
Test Name: Built-in Sort, Executions Per Second: 7650.01806640625
Test Name: Radix Bucket Sort , Executions Per Second: 7337.00048828125
Test Name: Insertion Sort, Executions Per Second: 3709.265625
Test Name: Bubble Sort, Executions Per Second: 3211.2890625
Test Name: Selection Sort, Executions Per Second: 2822.265625
```
Please note that the last three test results seem to be missing their `Browser` and `DevicePlatform` values.

Also, please let me know if you would like to perform any specific analysis or calculations on this data, such as calculating the average execution time for each test type or finding the maximum/minimum execution times.

Related benchmarks:

Javascript Sorting Algorithms 3.0 (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 Iterative quick sort

Created: one year ago by: Guest

Jump 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

Iterative quick sort

Suite status: <idle, ready to run>

Experimental features:

Fastest: N/A

Slowest: N/A

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