Run results for: Sorting Test: Tim Sort

Run details:

User agent: Mozilla/5.0 (Linux; Android 13) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/113.0.0.0 Mobile Safari/537.36

Browser: Chrome Mobile 113

Operating system: Android

Device Platform: Mobile

Date tested: one year ago

Test name	Executions per second
Tim Sort	4576.9 Ops/sec
Quick Sort	3858.3 Ops/sec

Script Preparation code:

function randomNumber(min, max) {
	return Math.floor(Math.random() * (max + 1 + Math.abs(min))) + min
}
function newArr(lengths = 5, min = 0, max = 10) {
	let newArr = []
  for (let i = 0; i < lengths; i++) {
  	newArr.push(randomNumber(min, max))
  }
  return newArr
}


function insertionSort(arr, left, right) {
  for (let i = left + 1; i <= right; i++) {
    let temp = arr[i];
    let j = i - 1;
    while (j >= left && arr[j] > temp) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = temp;
  }
}

function merge(arr, l, m, r) {
  let len1 = m - l + 1;
  let len2 = r - m;
  let left = new Array(len1);
  let right = new Array(len2);
  for (let i = 0; i < len1; i++) left[i] = arr[l + i];
  for (let i = 0; i < len2; i++) right[i] = arr[m + 1 + i];

  let i = 0;
  let j = 0;
  let k = l;

  while (i < len1 && j < len2) {
    if (left[i] <= right[j]) {
      arr[k] = left[i];
      i++;
    } else {
      arr[k] = right[j];
      j++;
    }
    k++;
  }

  while (i < len1) {
    arr[k] = left[i];
    k++;
    i++;
  }

  while (j < len2) {
    arr[k] = right[j];
    k++;
    j++;
  }
}

function timSort(arr) {
  const MIN_RUN = 32;
  const n = arr.length;

  for (let i = 0; i < n; i += MIN_RUN) {
    insertionSort(arr, i, Math.min(i + MIN_RUN - 1, n - 1));
  }

  for (let size = MIN_RUN; size < n; size = 2 * size) {
    for (let left = 0; left < n; left += 2 * size) {
      let mid = left + size - 1;
      let right = Math.min(left + 2 * size - 1, n - 1);

      if (mid < right) {
        merge(arr, left, mid, right);
      }
    }
  }

  return arr;
}

function quickSort(arr, left = 0, right = arr.length - 1) {
  if (left < right) {
    const pivotIndex = partition(arr, left, right);

    quickSort(arr, left, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, right);
  }
  return arr;
}

function partition(arr, left, right) {
  const pivot = arr[right];
  let i = left;

  for (let j = left; j < right; j++) {
    if (arr[j] < pivot) {
      [arr[i], arr[j]] = [arr[j], arr[i]];
      i++;
    }
  }

  [arr[i], arr[right]] = [arr[right], arr[i]];
  return i;
}

Tests:

Tim Sort
const sortedArr = timSort(newArr(200,-5000,5000))
Quick Sort
const sortedArr = quickSort(newArr(200,-5000,5000))

Run results for: Sorting Test: Tim Sort

Tim Sort testing

Tim Sort

Quick Sort