Sorting

Benchmark publishedon

Setup

function randomInts(size, max) {
  max = max || size * 10;
  const arr = new Array(size);
  for (let i = 0; i < size; i++) arr[i] = Math.floor(Math.random() * max);
  return arr;
}

function sortedAsc(size) {
  const arr = new Array(size);
  for (let i = 0; i < size; i++) arr[i] = i;
  return arr;
}

function sortedDesc(size) {
  const arr = new Array(size);
  for (let i = 0; i < size; i++) arr[i] = size - i;
  return arr;
}

function nearlySorted(size, swapRatio) {
  const arr = sortedAsc(size);
  const swaps = Math.max(1, Math.floor(size * (swapRatio || 0.03)));
  for (let i = 0; i < swaps; i++) {
    const a = Math.floor(Math.random() * size);
    const b = Math.floor(Math.random() * size);
    const t = arr[a]; arr[a] = arr[b]; arr[b] = t;
  }
  return arr;
}

function fewUnique(size, uniqueCount) {
  uniqueCount = uniqueCount || 8;
  const arr = new Array(size);
  for (let i = 0; i < size; i++) arr[i] = Math.floor(Math.random() * uniqueCount);
  return arr;
}

// ---- Pick the dataset every test case below will sort ----
// Swap this one line to change what ALL test cases run against.
const DATA_SIZE = 2_500;
const dataset = randomInts(DATA_SIZE);

Test Runner

Initializing...

Testing in
Test CaseOps/sec
Bubble sort
function bubbleSort(arr) {
  const n = arr.length;
  for (let i = 0; i < n - 1; i++) {
    let swapped = false;
    for (let j = 0; j < n - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        const t = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = t;
        swapped = true;
      }
    }
    if (!swapped) break;
  }
  return arr;
}

bubbleSort([...dataset]);
ready
Insertion sort
function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    const key = arr[i];
    let j = i - 1;
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = key;
  }
  return arr;
}

insertionSort([...dataset]);
ready
Selection sort
function selectionSort(arr) {
  const n = arr.length;
  for (let i = 0; i < n - 1; i++) {
    let min = i;
    for (let j = i + 1; j < n; j++) if (arr[j] < arr[min]) min = j;
    if (min !== i) { const t = arr[i]; arr[i] = arr[min]; arr[min] = t; }
  }
  return arr;
}

selectionSort([...dataset]);
ready
Shell sort
function shellSort(arr) {
  const n = arr.length;
  for (let gap = Math.floor(n / 2); gap > 0; gap = Math.floor(gap / 2)) {
    for (let i = gap; i < n; i++) {
      const temp = arr[i];
      let j = i;
      while (j >= gap && arr[j - gap] > temp) {
        arr[j] = arr[j - gap];
        j -= gap;
      }
      arr[j] = temp;
    }
  }
  return arr;
}

shellSort([...dataset]);
ready
Merge sort
function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const mid = arr.length >> 1;
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  const out = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length) {
    out.push(left[i] <= right[j] ? left[i++] : right[j++]);
  }
  while (i < left.length) out.push(left[i++]);
  while (j < right.length) out.push(right[j++]);
  return out;
}

mergeSort([...dataset]);
ready
Quick sort random pivot
function quickSortRandomPivot(arr, lo, hi) {
  if (lo === undefined) { lo = 0; hi = arr.length - 1; }
  if (lo >= hi) return arr;
  const p = lo + Math.floor(Math.random() * (hi - lo + 1));
  let t = arr[p]; arr[p] = arr[hi]; arr[hi] = t;
  const pivot = arr[hi];
  let i = lo - 1;
  for (let j = lo; j < hi; j++) {
    if (arr[j] < pivot) { i++; t = arr[i]; arr[i] = arr[j]; arr[j] = t; }
  }
  i++;
  t = arr[i]; arr[i] = arr[hi]; arr[hi] = t;
  quickSortRandomPivot(arr, lo, i - 1);
  quickSortRandomPivot(arr, i + 1, hi);
  return arr;
}

quickSortRandomPivot([...dataset]);
ready
Quick sort last pivot
function quickSortLastPivot(arr, lo, hi) {
  if (lo === undefined) { lo = 0; hi = arr.length - 1; }
  if (lo >= hi) return arr;
  const pivot = arr[hi];
  let i = lo - 1;
  for (let j = lo; j < hi; j++) {
    if (arr[j] < pivot) { i++; const t = arr[i]; arr[i] = arr[j]; arr[j] = t; }
  }
  i++;
  const t = arr[i]; arr[i] = arr[hi]; arr[hi] = t;
  quickSortLastPivot(arr, lo, i - 1);
  quickSortLastPivot(arr, i + 1, hi);
  return arr;
}

quickSortLastPivot([...dataset]);
ready
Heap sort
function heapSort(arr) {
  const n = arr.length;
  function heapify(size, i) {
    let largest = i, l = 2 * i + 1, r = 2 * i + 2;
    if (l < size && arr[l] > arr[largest]) largest = l;
    if (r < size && arr[r] > arr[largest]) largest = r;
    if (largest !== i) {
      const t = arr[i]; arr[i] = arr[largest]; arr[largest] = t;
      heapify(size, largest);
    }
  }
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) heapify(n, i);
  for (let i = n - 1; i > 0; i--) {
    const t = arr[0]; arr[0] = arr[i]; arr[i] = t;
    heapify(i, 0);
  }
  return arr;
}

heapSort([...dataset]);
ready
Native sort
function nativeSort(arr) {
  return arr.sort((a, b) => a - b);
}

nativeSort([...dataset]);
ready

Revisions

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

Revision 1
publishedon