Sorting Algorithms (v26)

Revision 26 of this benchmark created by Mo on

Description

Sort many values, for one value go to http://jsperf.com/sorting-algorithms-one-dirty

Change in version 26: Each algorithm has to sort 1 million floats (0.0-1.0) rather than 1 thousand integers.

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
  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
//It should NOT be running at the EXACT same speed as the inplace version due to the number of changes, but it does on jsPerf for some reason....
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 mysort(arr) {
  var len = arr.length;
  var lp = -1;

  for (var i=0; i<len-1; ) {
    var p1 = arr[i], p2 = arr[i+1];
    if (p1 > p2) {
      arr[i] = p2; arr[i+1] = p1; lp = i; i -= 1;
      if (i < 0) { 
        i = 0;
      }
    }
    else if (lp == -1) { i++; }
    else { i = lp + 1; lp++ }
  }
  return arr;
}
var input = [];
var qty = 1000000; //1 million floats
for (var i = 0; i < qty; i++) {
  input[i] = Math.random();
}
</script>

Teardown


    /*
    //I commented this out since each algorithm produces correct output. Although this test is good programming practice, I'm really impatient to see results
    
    for (var i = 0; i < qty; i++) {
      if (ret[i] > ret[i] + 1) {
        throw Error('Array is not sorted');
      }
    }
    */

Test runner

Ready to run.

Testing in
TestOps/sec
Built-in Sort
ret = builtin_sort(input.slice(0));
ready
Bubble Sort
ret = bubble_sort(input.slice(0));
ready
Naive Quicksort
ret = naive_quicksort(input.slice(0));
ready
Inplace Quicksort
ret = inplace_quicksort(input.slice(0), 0, input.length);
ready
Heap Sort
ret = heapSort(input.slice(0));
ready
Merge Sort
ret = merge_sort(input.slice(0));
ready
Shell Sort
ret = shell_sort(input.slice(0));
ready
Comb Sort
ret = comb_sort(input.slice(0));
ready
Insertion Sort
ret = insertion_sort(input.slice(0));
ready
Fast QuickSort
ret = fast_quicksort(input.slice(0));
ready
MySort
ret = mysort(input.slice(0));
ready

Revisions

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