Sorting Algorithms (v4)

Revision 4 of this benchmark created by Jeff Avallone on

Description

Added native (lexicographic/dictionary) Array sort

Preparation HTML

<script>
  function swap(ary, a, b) {
      var t = ary[a];
      ary[a] = ary[b];
      ary[b] = t;
  }
  
  // just for reference, native sort without comparator function
  // this gives the wrong result with numeric array entries
  function native_dictionary_sort(ary) {
    return ary.sort();
  }
  
  // Built-in with comparison function (default sorting is "dictionary-style")
  function builtin_sort(ary) {
      return ary.sort(function(a, b) {
          if (a === b) {
              return 0;
          }
  
          return (a < b) ? -1 : 1;
      });
  }
  
  // Built-in with smaller comparison function
  function builtin_sort2(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;
  }
  
  // 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 pivotValue = ary[pivotIndex],
          storeIndex = start,
          i;
  
      swap(ary, pivotIndex, end - 1);
  
      for (i = start; i < end - 1; i++) {
          if (ary[i] < pivotValue) {
              swap(ary, i, storeIndex);
  
              storeIndex++;
          }
      }
  
      swap(ary, storeIndex, end - 1);
  
      return storeIndex;
  }
  
  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;
  }
</script>

Setup

var input = [];
    for (var i = 0; i < 1000000; i++) {
      input[i] = Math.round(Math.random() * 1000000);
    }

Test runner

Ready to run.

Testing in
TestOps/sec
Built-in Sort (comparator)
builtin_sort(input.slice(0));
ready
Bubble Sort
bubble_sort(input.slice(0));
ready
Naive Quicksort
naive_quicksort(input.slice(0));
ready
Inplace Quicksort
inplace_quicksort(input.slice(0), 0, input.length);
ready
Heap Sort
heapSort(input.slice(0));
ready
Merge Sort
merge_sort(input.slice(0));
ready
Shell Sort
shell_sort(input.slice(0));
ready
Native Dictionary Sort
native_dictionary_sort(input.slice(0));
ready
Built-in Sort (smaller comparator)
builtin_sort2(input.slice(0));
ready

Revisions

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