Benchmark: Sorting algorithms comparison (source: https://www.measurethat.net/Benchmarks/Show/3549/0/javascript

Sorting algorithms comparison (source: https://www.measurethat.net/Benchmarks/Show/3549/0/javascript (version: 2)

Comparing performance of: Inplace Quicksort vs Merge Sort vs Built-in Sort vs Heap Sort vs Shell Sort vs Insertion Sort vs mSort vs Comb Sort vs Radix Bucket Sort vs Fast QuickSort vs Naive Quicksort vs Bubble Sort

Created: 6 years ago by: Registered User

Jump to the latest result

Script Preparation code:

var input = [];
for (var i = 0; i < 100; i++) {
  input[i] = Math.round(Math.random() * 1000000);
}

function swap(ary, a, b) {
  var t = ary[a];
  ary[a] = ary[b];
  ary[b] = t;
}

// Built-in with comparison function (default sorting is "dictionary-style")
function builtin_sort(ary) {
  return ary.sort(function(a, b) {
    return a - b;
  });
}

// Bubble Sort
function bubble_sort(ary) {
  var a, b;
  for (a = 0; a < ary.length; a++) {
    for (b = a + 1; b < ary.length; b++) {
      if (ary[a] > ary[b]) {
        swap(ary, a, b);
      }
    }
  }

  return ary;
}
//Insertion sort
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] <= value) break;
      ary[j + 1] = ary[j];
    }
    ary[j + 1] = value;
  }
  return ary;
}

// Naive (but understandable) quicksort (memory hog)
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] < pivot) {
      less.push(ary[i]);
    } else {
      greater.push(ary[i]);
    }
  }

  less = naive_quicksort(less);
  greater = naive_quicksort(greater);

  return less.concat(pivot, greater);
}

// In place quicksort
function inplace_quicksort_partition(ary, start, end, pivotIndex) {
  var i = start,
    j = end;
  var pivot = ary[pivotIndex];

  while (true) {
    while (ary[i] < pivot) {
      i++;
    }
    j--;
    while (pivot < ary[j]) {
      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;
}

// Heap sort
function heapSort(ary) {
  heapify(ary);

  for (var end = ary.length - 1; end > 0; end--) {
    swap(ary, end, 0);
    shiftDown(ary, 0, end - 1);
  }

  return ary;
}

function heapify(ary) {
  for (var start = (ary.length >> 1) - 1; start >= 0; start--) {
    shiftDown(ary, start, ary.length - 1);
  }
}

function shiftDown(ary, start, end) {
  var root = start,
    child,
    s;

  while (root * 2 + 1 <= end) {
    child = root * 2 + 1;
    s = root;

    if (ary[s] < ary[child]) {
      s = child;
    }

    if (child + 1 <= end && ary[s] < ary[child + 1]) {
      s = child + 1;
    }

    if (s !== root) {
      swap(ary, root, s);
      root = s;
    } else {
      return;
    }
  }
}

// Merge sort
function merge_sort(ary) {
  if (ary.length <= 1) {
    return ary;
  }

  var m = ary.length >> 1;

  var left = ary.slice(0, m),
    right = ary.slice(m);

  return merge(merge_sort(left), merge_sort(right));
}

function merge(left, right) {
  var result = [],
    li = 0,
    ri = 0;

  while (li < left.length || ri < right.length) {
    if (li < left.length && ri < right.length) {
      if (left[li] <= right[ri]) {
        result.push(left[li]);
        li++;
      } else {
        result.push(right[ri]);
        ri++;
      }
    } else if (li < left.length) {
      result.push(left[li]);
      li++;
    } else if (ri < right.length) {
      result.push(right[ri]);
      ri++;
    }
  }

  return result;
}

// Shell sort
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] > t) {
        ary[j] = ary[j - inc];
        j -= inc;
      }
      ary[j] = t;
    }
    inc = Math.round(inc / 2.2);
  }

  return ary;
}
//Comb Sort (Basically bubblesort with a small modification, but heaps faster)
function comb_sort(ary) {
  var gap = ary.length;
  while (true) {
    gap = newgap(gap);
    var swapped = false;
    for (var i = 0, l = ary.length; i < l; i++) {
      var j = i + gap;
      if (ary[i] < ary[j]) {
        swap(ary, i, j);
        swapped = true;
      }
    }
    if (gap == 1 && !swapped) break;
  }
  return ary;
}
function newgap(gap) {
  gap = ((gap * 10) / 13) | 0;
  if (gap == 9 || gap == 10) gap = 11;
  if (gap < 1) gap = 1;
  return gap;
}
//faster quicksort using a stack to eliminate recursion, sorting inplace to reduce memory usage, and using insertion sort for small partition sizes
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] > t) {
        ary[j] = ary[j - inc];
        j -= inc;
      }
      ary[j] = t;
    }
    inc = Math.round(inc / 2.2);
  }

  return ary;
}

function mSort(list) {
  if (list.length < 14) {
    return insertion_sort(list);
  }

  var half = Math.floor(list.length / 2);
  var a = mSort(list.slice(0, half));
  var b = mSort(list.slice(half, list.length));
  var aCount = 0;
  var bCount = 0;
  var returnList = [];

  while (true) {
    if (a[aCount] <= b[bCount]) {
      returnList.push(a[aCount]);
      aCount++;
      if (aCount === a.length) {
        returnList = returnList.concat(b.slice(bCount, b.length));
        break;
      }
    } else {
      returnList.push(b[bCount]);
      bCount++;
      if (bCount === b.length) {
        returnList = returnList.concat(a.slice(aCount, a.length));
        break;
      }
    }
  }
  return returnList;
}

function bubbleSort(items) {
  var length = items.length;
  for (var i = 0; i < length; i++) {
    //Number of passes
    for (var j = 0; j < length - i - 1; j++) {
      //Notice that j < (length - i)
      //Compare the adjacent positions
      if (items[j] > items[j + 1]) {
        //Swap the numbers
        var tmp = items[j]; //Temporary variable to hold the current number
        items[j] = items[j + 1]; //Replace current number with adjacent number
        items[j + 1] = tmp; //Replace adjacent number with current number
      }
    }
  }
}

function radixBucketSort(arr) {
  var idx1, idx2, idx3, len1, len2, radix, radixKey;
  var radices = {},
    buckets = {},
    num,
    curr;
  var currLen, radixStr, currBucket;

  len1 = arr.length;
  len2 = 10; // radix sort uses ten buckets

  // find the relevant radices to process for efficiency
  for (idx1 = 0; idx1 < len1; idx1++) {
    radices[arr[idx1].toString().length] = 0;
  }

  // loop for each radix. For each radix we put all the items
  // in buckets, and then pull them out of the buckets.
  for (radix in radices) {
    // put each array item in a bucket based on its radix value
    len1 = arr.length;
    for (idx1 = 0; idx1 < len1; idx1++) {
      curr = arr[idx1];
      // item length is used to find its current radix value
      currLen = curr.toString().length;
      // only put the item in a radix bucket if the item
      // key is as long as the radix
      if (currLen >= radix) {
        // radix starts from beginning of key, so need to
        // adjust to get redix values from start of stringified key
        radixKey = curr.toString()[currLen - radix];
        // create the bucket if it does not already exist
        if (!buckets.hasOwnProperty(radixKey)) {
          buckets[radixKey] = [];
        }
        // put the array value in the bucket
        buckets[radixKey].push(curr);
      } else {
        if (!buckets.hasOwnProperty("0")) {
          buckets["0"] = [];
        }
        buckets["0"].push(curr);
      }
    }
    // for current radix, items are in buckets, now put them
    // back in the array based on their buckets
    // this index moves us through the array as we insert items
    idx1 = 0;
    // go through all the buckets
    for (idx2 = 0; idx2 < len2; idx2++) {
      // only process buckets with items
      if (buckets[idx2] != null) {
        currBucket = buckets[idx2];
        // insert all bucket items into array
        len1 = currBucket.length;
        for (idx3 = 0; idx3 < len1; idx3++) {
          arr[idx1++] = currBucket[idx3];
        }
      }
    }
    buckets = {};
  }
}

Tests:

Inplace Quicksort
inplace_quicksort(input.slice(0), 0, input.length);
Merge Sort
merge_sort(input.slice(0));
Built-in Sort
builtin_sort(input.slice(0));
Heap Sort
heapSort(input.slice(0));
Shell Sort
shell_sort(input.slice(0));
Insertion Sort
insertion_sort(input.slice(0));
mSort
mSort(input.slice(0));
Comb Sort
comb_sort(input.slice(0));
Radix Bucket Sort
radixBucketSort(input.slice(0));
Fast QuickSort
fast_quicksort(input.slice(0));
Naive Quicksort
naive_quicksort(input.slice(0));
Bubble Sort
bubbleSort(input.slice(0));

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Test case name	Result
Inplace Quicksort
Merge Sort
Built-in Sort
Heap Sort
Shell Sort
Insertion Sort
mSort
Comb Sort
Radix Bucket Sort
Fast QuickSort
Naive Quicksort
Bubble Sort

Fastest: N/A

Slowest: N/A

Latest run results:

No previous run results

This benchmark does not have any results yet. Be the first one to run it!

Autogenerated LLM Summary (model llama3.2:3b, generated one year ago):

LLMs can make mistakes. Check important info.

Related benchmarks: