Comparison of merge sort with a new trimergesort algorithm

JavaScript performance comparison

Test case created by Alessandro Nunes

Info

The sorting problem is one of the most fundamental problems in computer science. This paper is concerned with a new Tri-merge sorting algorithm. This is a modification of Merge sort. It is competitive with the fastest shorting algorithms, especially when the number of elements to be sorted is too large. Compared with the preceding Merge sort, Tri-merge sort is more robust. It is not only faster on random inputs, but also avoids extreme comparisons. The empirical results show that Tri-merge sort is faster than Merge sort. This reduces the time complexity and makes the algorithm faster.

COMPARISON OF MERGE SORT WITH A NEW TRI-MERGE SORTING ALGORITHM Jannatun Nayeem1 and Md. Abu Salek2

Preparation code

 
<script>
Benchmark.prototype.setup = function() {
    var unsorted = randomItens(300000);
   
    function randomItens(total) {
      var max = total * 10;
      var arrayTemp = [];
   
      for (i = 0; i < total; i++) {
        arrayTemp.push(ramdomUnique(max, arrayTemp));
      }
   
      return arrayTemp;
    }
   
    function ramdomUnique(max, array) {
   
      var randomNumber = Math.floor(Math.random() * (max + 1));
   
      if (array.indexOf(randomNumber) !== -1) {
        return ramdomUnique(max, array);
      } else {
        return randomNumber;
      }
   
    }
};
</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
temp = unsorted;
mergeSort(temp);

function mergeSort(items) {
  operation++;

  // Terminal case: 0 or 1 item arrays don't need sorting
  if (items.length < 2) {
    return items;
  }

  var middle = Math.floor(items.length / 2),
      left = items.slice(0, middle),
      right = items.slice(middle);

  return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
  var result = [],
      il = 0,
      ir = 0;

  while (il < left.length && ir < right.length) {
    if (left[il] < right[ir]) {
      result.push(left[il++]);
    } else {
      result.push(right[ir++]);
    }
  }

  return result.concat(left.slice(il)).concat(right.slice(ir));
}
pending…
Tri-Merge Sort
temp = unsorted;
triMergeSort(unsorted, 0, unsorted.length - 1);

triMergeSort(items);

function triMergeSort(a, L, R) {
  operation++;

  //console.log(totalTemp+'triMergeSort','L',L,'R',R);
  var n = R - L + 1;

  //console.log('n',n);
  if (n > 2) {

    var m1 = L + Math.floor(n / 3);
    var m2 = L + 2 * Math.floor(n / 3);

    //console.log('n > 2');
    //console.log('m1',m1);
    //console.log('m2',m2);
    //console.log(totalTemp+'merge1',L, m1-1);
    a = triMergeSort(a, L, m1 - 1);
    //console.log(totalTemp+'merge2',m1, m2-1);
    a = triMergeSort(a, m1, m2 - 1);
    //console.log(totalTemp+'merge3',m2, R);
    a = triMergeSort(a, m2, R);

    a = triMerge(a, L, m1, m2, R);

  } else if (n == 2) {

    if (a[L] > a[R]) {

      temp = a[L];
      a[L] = a[R];
      a[R] = temp;

    }

  }
  return a;
}

function triMerge(a, L, m1, m2, R) {

  var TempArray = [];
  var n = R - L + 1;

  var i1 = L;
  var i2 = m1;
  var i3 = m2;

  if (n > 2) {
    while (i1 < m1 && i2 < m2 && i3 < R + 1) {

      if (a[i1] < a[i2] && a[i1] < a[i3]) {
        TempArray.push(a[i1]);
        i1++;
      } else if (a[i2] < a[i1] && a[i2] < a[i3]) {
        TempArray.push(a[i2]);
        i2++;
      } else if (a[i3] < a[i1] && a[i3] < a[i2]) {
        TempArray.push(a[i3]);
        i3++;
      }
    }
    while (i1 < m1 && i2 < m2) {
      //console.log('while2');
      if (a[i1] < a[i2]) {
        TempArray.push(a[i1]);
        i1++;
      } else {
        TempArray.push(a[i2]);
        i2++;
      }
    }
    while (i2 < m2 && i3 < R + 1) {
      //console.log('while3');
      if (a[i2] < a[i3]) {
        TempArray.push(a[i2]);
        i2++;
      } else {
        TempArray.push(a[i3]);
        i3++;
      }
    }
    while (i1 < m1 && i3 < R + 1) {
      //console.log('while4');
      if (a[i1] < a[i3]) {
        TempArray.push(a[i1]);
        i1++;
      } else {
        TempArray.push(a[i3]);
        i3++;
      }
    }
    while (i1 < m1) {
      //console.log('while5');
      TempArray.push(a[i1]);
      i1++;
    }
    while (i2 < m2) {
      //console.log('while6');
      TempArray.push(a[i2]);
      i2++;
    }
    while (i3 < R + 1) {
      //console.log('while7');
      TempArray.push(a[i3]);
      i3++;
    }
  }

  for (i = 0; i < R - L + 1; i++) {
    //console.log('for');
    a[L + i] = TempArray[i];
  }

  //console.log(TempArray);
  return a;
}
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

Add a comment