Javascript Sort

JavaScript performance comparison

Test case created by Adam Lu

Preparation code

 
<script>
Benchmark.prototype.setup = function() {
    function merge(left, right) {
      var result = [];
      while (left.length > 0 && right.length > 0) {
        if (left[0] < right[0]) {
          result.push(left.shift());
        } else {
          result.push(right.shift());
        }
      }
   
      return result.concat(left).concat(right);
   
    }
   
    function mergeSort(arr) {
   
      if (arr.length <= 1) {
        return arr;
      }
   
      var middle = Math.floor(arr.length / 2);
      var left = arr.slice(0, middle);
      var right = arr.slice(middle);
   
      return merge(mergeSort(left), mergeSort(right));
   
    }
   
    function quickSort(arr) {
      if (arr.length <= 1) {
        return arr;
      }
      var pivot = arr.splice(Math.floor(arr.length / 2), 1)[0];
      var left = [];
      var right = [];
      for (var i = 0; i < arr.length; i++) {
        if (arr[i] < pivot) {
          left.push(arr[i]);
        } else {
          right.push(arr[i]);
        }
      }
   
      return quickSort(left).concat([pivot], quickSort(right));
    }
   
   
    function bubbleSort(arr) {
      if (arr.length <= 1) {
        return arr;
      }
      for (var i = arr.length - 1; i > 0; i--) {
        for (var j = i - 1; j >= 0; j--) {
          if (arr[j] < arr[j - 1]) {
            var tmp = arr[j];
            arr[j] = arr[j - 1];
            arr[j - 1] = tmp;
          }
        }
      }
   
      return arr;
    }
   
    function selectSort(arr) {
      var min, tmp;
      for (var i = 0; i < arr.length; i++) {
        min = i;
        for (var j = i + 1; j < arr.length; j++) {
          if (arr[min] > arr[j]) {
            min = j;
          }
        }
        if (min != i) {
          tmp = arr[i];
          arr[i] = arr[min];
          arr[min] = tmp;
        }
      }
   
      return arr;
    }
   
    function insertSort(arr) {
      for (var i = 1; i < arr.length; i++) {
        var tmp = arr[i],
            j = i;
        while (arr[j - 1] > tmp) {
          arr[j] = arr[j - 1];
          --j;
        }
        arr[j] = tmp;
      }
   
      return arr;
    }
};
</script>

Test runner

Warning! For accurate results, please disable Firebug before running the tests. (Why?)

Java applet disabled.

Testing in unknown unknown
Test Ops/sec
Merge Sort
var arr = [1, 3, 5, 2, 4, 8, 7];
mergeSort(arr);
pending…
Quick Sort
var arr = [1, 3, 5, 2, 4, 8, 7];
quickSort(arr);
pending…
Bubble Sort
var arr = [1, 3, 5, 2, 4, 8, 7];
bubbleSort(arr);
pending…
Select Sort
var arr = [1, 3, 5, 2, 4, 8, 7];
selectSort(arr);
pending…
Insert Sort
var arr = [1, 3, 5, 2, 4, 8, 7];
insertSort(arr);
pending…
Array Sort
var arr = [1, 3, 5, 2, 4, 8, 7];
arr.sort(function(a, b) {
  return a - b;
});
pending…

Compare results of other browsers

Revisions

You can edit these tests or add even more tests to this page by appending /edit to the URL. Here’s a list of current revisions for this page:

2 comments

Dave commented :

You need to run this on an array of hundreds or even thousands of elements in order to get an accurate picture; Insert, Select and Bubble start to fall off very badly once the set gets properly big.

Zex commented :

You messed up QuickSort. Why did you push elements into a subarray, instead of just passing through them and swapping them, like in the original algorithm? Push operation is slow. No wonder that QuickSort is slowest when it's done the wrong way.

Add a comment