Run results for: SortingTests

Run details:

User agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/96.0.4664.93 Safari/537.36 Edg/96.0.1054.53

Browser: Chrome 96

Operating system: Windows

Device Platform: Desktop

Date tested: 3 years ago

Test name	Executions per second
builtin_sort	118071.5 Ops/sec
insertion_sort	210244.2 Ops/sec
shell_sort	218406.5 Ops/sec
inplace_quicksort	32554.6 Ops/sec
fast_quicksort	75321.8 Ops/sec

Script Preparation code:

const max =100;
const type = 0;
 unsorted= [];
const sample = 1100000000;
while (unsorted.length < max) {
	const count = unsorted.length;
	let t = 0;
	if(type === 0) {
		t = Math.floor(Math.random() * (sample*2)) + sample;
	} else if(type === 1) {
		t = sample  + (count*1000);
	} else if(type === 2) {
		t = sample  - (count*1000);
	}
	if(unsorted.findIndex(it => it.timestamp === t) === -1) {
		 unsorted.push({
         proceedingTime: 20,
         maxWaitingTime: 'asjdsjadsajdjsadadasd',
         maxWaitingTimeEnabled: true,
         alertWaitingDelay: 60,
         maintainPositionTime: '2387423784723847823487',
         maintainWaitingPosition: true,
         timestamp: t
      });
   }
}

function builtin_sort(unsorted) {
  return unsorted.sort((a, b) => {
    return a.timestamp - b.timestamp;
  });
}

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].timestamp < pivot.timestamp) {
      less.push(ary[i]);
    } else {
      greater.push(ary[i]);
    }
  }
  less = naive_quicksort(less);
  greater = naive_quicksort(greater);
  return less.concat(pivot, greater);
}

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].timestamp <= value.timestamp)
        break;
      ary[j + 1] = ary[j];
    }
    ary[j + 1] = value;
  }
  return ary;
}

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].timestamp > t.timestamp) {
        ary[j] = ary[j - inc];
        j -= inc;
      }
      ary[j] = t;
    }
    inc = Math.round(inc / 2.2);
  }
  return ary;
}

function inplace_quicksort_partition(ary, start, end, pivotIndex) {
  var i = start, j = end;
  var pivot = ary[pivotIndex];
  while (true) {
    while (ary[i].timestamp < pivot.timestamp) { i++ };
    j--;
    while (pivot.timestamp < ary[j].timestamp) { 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;
}

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].timestamp > t.timestamp) {
        ary[j] = ary[j - inc];
        j -= inc;
      }
      ary[j] = t;
    }
    inc = Math.round(inc / 2.2);
  }
  return ary;
}

function swap(ary, a, b) {
  var t = ary[a];
  ary[a] = ary[b];
  ary[b] = t;
}

Tests:

builtin_sort
const sorted = builtin_sort(unsorted.slice());
insertion_sort
const sorted = insertion_sort(unsorted.slice());
shell_sort
const sorted = shell_sort(unsorted.slice());
inplace_quicksort
const un = unsorted.slice(); const sorted = inplace_quicksort(un, 0, un.length-1);
fast_quicksort
const sorted = fast_quicksort(unsorted.slice());