sort-algorithms (v41)

Revision 41 of this benchmark created on

Description

Comparing native, bubble, insertion, selection, merge, adaptive merge, and quick sort algorithms on a random and sorted arrays.

Preparation HTML

<script src="https://rawgithub.com/escherba/algorithms-in-javascript/master/src/common.js">
</script>
<script src="https://rawgithub.com/escherba/algorithms-in-javascript/master/src/bubble-sort.js">
</script>
<script src="https://rawgithub.com/escherba/algorithms-in-javascript/master/src/insertion-sort.js">
</script>
<script src="https://rawgithub.com/escherba/algorithms-in-javascript/master/src/merge-sort.js">
</script>
<script>
aij.mergeSort2 = (function(){
    "use strict";

    function simpleMerge(a, from, pivot, to, buffer) {
      var i = -1;
      while (++i < to - pivot) {
        buffer[i] = a[i + pivot];
      }
      --i;
      --pivot;
      while (i >= 0) {
        --to;
        if (pivot >= from && buffer[i] < a[pivot]) {
          a[to] = a[pivot];
          --pivot;
        } else {
          a[to] = buffer[i];
          --i;
        }
      }
    }

    function mergeSort(a, from, to, buffer) {
      if (to - from > 1) {
        var middle = from + Math.floor((to - from) / 2);
        mergeSort(a, from, middle, buffer);
        mergeSort(a, middle, to, buffer);
        simpleMerge(a, from, middle, to, buffer);
      }
      return a;
    }

    return function(items) { return mergeSort(items, 0, items.length, items.slice(0, Math.floor((items.length + 1) / 2))); };
})();


var stableQuickSort = function (array, from, to, buffer, buffer2) {
  while (to - from > 1) {
    var pivotIndex = from + Math.floor((to - from) / 2);
    var pivot = array[pivotIndex];
    var i = from - 1;
    var k = from - 1;
    var l = -1;
    var m = -1;
    while (++i < to) {
      var c = array[i] < pivot ? -1 : (pivot < array[i] ? 1 : 0);
      if (c < 0) {
        array[++k] = array[i];
      } else if (c > 0) {
        buffer[++l] = array[i];
      } else {
        buffer2[++m] = array[i];
      }
    }
    ++k;
    ++m;
    ++l;
    i = -1;
    while (++i < m) {
      array[k + i] = buffer2[i];
    }
    i = -1;
    while (++i < l) {
      array[k + m + i] = buffer[i];
    }
    if (k - from < to - (k + m)) {
      stableQuickSort(array, from, k, buffer, buffer2);
      from = k + m;
    } else {
      stableQuickSort(array, k + m, to, buffer, buffer2);
      to = k;
    }
  }
  return array;
};
</script>
<script src="https://rawgithub.com/escherba/algorithms-in-javascript/master/src/adaptive-sort.js">
</script>
<script src="https://rawgithub.com/escherba/algorithms-in-javascript/master/src/quickmiddle-sort.js">
</script>
<script src="https://rawgithub.com/escherba/algorithms-in-javascript/master/src/selection-sort.js">
</script>
<script src="https://rawgithub.com/escherba/algorithms-in-javascript/master/src/flashsort.js">
</script>
<script src="https://rawgithub.com/escherba/algorithms-in-javascript/master/src/heap-sort.js">
</script>

Setup

// Generate array with 100,000 random integers.
    testArrayLength = 100000;
    var unsortedTestArray = new Array(testArrayLength);
    for (var i = 0; i < testArrayLength; i++) {
      unsortedTestArray[i] = Math.floor(Math.random()*100000);
    }
    var sortedTestArray = unsortedTestArray.clone().sort(function compareNumbers(a, b) {
      return a - b;
    });

Teardown


    if (!result.compare(sortedTestArray)) {
       throw new Error("Array was not sorted");
    }

Test runner

Ready to run.

Testing in
TestOps/sec
Native
var result = unsortedTestArray.clone().sort(function compareNumbers(a, b) {
  return a - b;
});
ready
Heapsort
var result = aij.heapSort(unsortedTestArray.clone());
ready
AdaptiveSort
var result = aij.adaptiveSort(unsortedTestArray.clone());
ready
MergeSort
var result = aij.mergeSort(unsortedTestArray.clone());
ready
QuickSort
var result = aij.quickmiddleSort(unsortedTestArray.clone());
ready
Flashsort
var result = aij.flashSort(unsortedTestArray.clone());
ready
MergeSort2
var result = aij.mergeSort2(unsortedTestArray.clone());
ready
stableQuickSort
var result = stableQuickSort(unsortedTestArray.clone(), 0, unsortedTestArray.length, [], []);
ready
Native Sorted
var result = sortedTestArray.clone().sort(function compareNumbers(a, b) {
  return a - b;
});
ready
Heapsort Sorted
var result = aij.heapSort(sortedTestArray.clone());
ready
AdaptiveSort Sorted
var result = aij.adaptiveSort(sortedTestArray.clone());
ready
MergeSort Sorted
var result = aij.mergeSort(sortedTestArray.clone());
ready
QuickSort Sorted
var result = aij.quickmiddleSort(sortedTestArray.clone());
ready
Flashsort Sorted
var result = aij.flashSort(sortedTestArray.clone());
ready
MergeSort2 Sorted
var result = aij.mergeSort2(sortedTestArray.clone());
ready
Stable Quick Sort Sorted
var result = stableQuickSort(sortedTestArray.clone(), 0, sortedTestArray.length, [], []);
ready

Revisions

You can edit these tests or add more tests to this page by appending /edit to the URL.