Sorting Algorithms (v8)

Revision 8 of this benchmark created on

Preparation HTML

<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
  // 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;
  }
  //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;
    }   
}
function newgap(gap) {
    gap = ((gap * 10) / 13) | 0;
    if(gap == 9 || gap == 10)
        gap = 11;
    if(gap < 1)
         gap = 1;
    return gap;
}
var left;
var right;
var stack;
//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) {
    stack = [];
    pushStack(0,ary.length);
    while(stack.length > 0) {
        popStack();
        while(true) {
            if( right - left + 1 > 15) {
                var pivot = (right + left) / 2 | 0;
                var pivotNewIndex = inplace_quicksort_partition(ary,left,right, pivot);
                if(right - pivotNewIndex < pivotNewIndex - left) {
                    pushStack(left,pivotNewIndex - 1);
                    left = pivotNewIndex + 1;
                } else {
                    pushStack(pivotNewIndex + 1, right);
                    right = pivotNewIndex - 1;
                }
            } else {
                //insertion sort is faster when the size is small enough
                insertion_sort_bound(ary, left, right);
                break;
            }
        }
    }
}
function insertion_sort_bound(ary,left,right) {
    var j;
    for(var i=left+1;i<right;i++) {
        var value = ary[i];
        for(j=i - 1;j>=9;j--) {
            if(ary[j] <= value) 
                break;
            ary[j+1] = ary[j];
        }
        ary[j+1] = value;
    }
}
function pushStack(a,b) {
var col = [a,b];
stack.push(col);
}
function popStack() {
var col = stack.pop();
left = col[0];
right = col[1];
}
</script>

Setup

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

Test runner

Ready to run.

Testing in
TestOps/sec
Built-in Sort
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
Comb Sort
comb_sort(input.slice(0));
ready
Insertion Sort
insertion_sort(input.slice(0));
ready
Fast QuickSort
fast_quicksort(input.slice(0));
ready

Revisions

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