Array.sort vs

JavaScript performance comparison

Test case created by nagtkk

Preparation code


      
      <script>
Benchmark.prototype.setup = function() {
  const compareDefault = (x, y) => x < y ? -1 : x > y ? 1 : 0;
  
  const med3 = (x, y, z, cmp) =>
      cmp(x, y) < 0 ?
          cmp(y, z) < 0 ? y : cmp(z, x) < 0 ? x : z :
          cmp(z, y) < 0 ? y : cmp(x, z) < 0 ? x : z;
  
  /*
  const quickSort = (a, cmp = compareDefault, i = 0, j = a.length) => {
      if (i < j) {
          let p = i, q = j - 1;
          const pivot = med3(a[p], a[p + ((q - p) >> 1)], a[q], cmp);
          for (; ; p++ , q--) {
              while (cmp(a[p], pivot) < 0) p++;
              while (cmp(pivot, a[q]) < 0) q--;
              if (p >= q) break;
              const t = a[p];
              a[p] = a[q];
              a[q] = t;
          }
          quickSort(a, cmp, i, p);
          quickSort(a, cmp, q + 1, j);
      }
      return a;
  };
  */
  
  const heapSort = (a, cmp = compareDefault, i = 0, j = a.length) => {
      const n = j - i;
      let k = 0;
      while (++k < n) {
          let c = k;
          const cv = a[c + i];
          while (c > 0) {
              const p = ((c + 1) >> 1) - 1;
              const pv = a[p + i];
              if (cmp(pv, cv) >= 0) break;
              a[c + i] = pv;
              c = p;
          }
          a[c + i] = cv;
      }
      while (--k > 0) {
          let p = 0;
          const pv = a[k + i];
          a[k + i] = a[i];
          for (; ;) {
              const cr = (p + 1) << 1;
              const cl = cr - 1;
              if (!(cl < k)) break;
              const c = (cr >= k || cmp(a[cl + i], a[cr + i]) >= 0) ? cl : cr;
              const cv = a[c + i];
              if (cmp(pv, cv) >= 0) break;
              a[p + i] = cv;
              p = c;
          }
          a[p + i] = pv;
      }
      return a;
  };
  
  const insertionSort = (a, cmp = compareDefault, i = 0, j = a.length) => {
      for (let p = i + 1; p < j; p++) {
          const v = a[p];
          let q = p, r = p - 1;
          if (cmp(v, a[i]) < 0)
              for (; i < q; q = r--) a[q] = a[r];
          else
              for (; cmp(v, a[r]) < 0; q = r--) a[q] = a[r];
          a[q] = v;
      }
      return a;
  };
  
  const ilog2 = n => {
      let d = 0;
      for (; n > 1; n >>>= 1) d++;
      return d;
  };
  
  const INTRO_MIN = 32;
  const introSort = (a, cmp = compareDefault, i = 0, j = a.length) => {
      const sub = (a, i, j, cmp, depth) => {
          if (j - i < INTRO_MIN) return insertionSort(a, cmp, i, j);
          if (depth-- <= 0) return heapSort(a, cmp, i, j);
          let p = i, q = j - 1;
          const pivot = med3(a[p], a[p + ((q - p) >> 1)], a[q], cmp);
          for (; ; p++ , q--) {
              while (cmp(a[p], pivot) < 0) p++;
              while (cmp(pivot, a[q]) < 0) q--;
              if (p >= q) break;
              const t = a[p];
              a[p] = a[q];
              a[q] = t;
          }
          sub(a, i, p, cmp, depth);
          sub(a, q + 1, j, cmp, depth);
          return a;
      };
  
      return sub(a, i, j, cmp, 2 * ilog2(j - i));
  };
  
  const genRandomArray = length =>
      Array.from({ length }, _ => ({
          value: ~~(Math.random() * length)
      }));
  const comparator = (a, b) => a.value - b.value;
  
  const size = 100000;
  const count = 5;
  const arrays = Array.from({length:count}, () => genRandomArray(size));

};
</script>

Test runner

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

Java applet disabled.

Testing in CCBot 2.0.0 / Other 0.0.0
Test Ops/sec
Array.sort
for (let array of arrays) {
  array.sort(comparator);
}
pending…
introSort (revised)
for (let array of arrays) {
  introSort(array, comparator);
}
pending…

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

Compare results of other browsers

0 Comments