Benchmark: Test Quick Insertion Sort3

Test Quick Insertion Sort3 (version: 2)

Port from jsperf(https://jsperf.com/sorting-algorithms/58)

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

Created: 2 years ago by: Registered User

Jump to the latest result

HTML Preparation code:

<script>
  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
      }
    }        
  }
}
  
  //https://stackoverflow.com/a/38979903/8769328
  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 = {};
    }
  }
  
  function quickInsertionSort(arr) {
  if (!arr || arr.length < 1) {
    return;
  }
  const stack = [];
  stack.push([0, arr.length, 2 * Math.floor(Math.log(arr.length) / Math.log(2))]);

  while (stack.length > 0) {
    const [start, end, depth] = stack[stack.length - 1];
    stack.pop();

    if (depth === 0) {
      shellSortBound(arr, start, end);
    } else {
      const pivot = Math.round((start + end) / 2);
      const pivotNewIndex = inplaceQuicksortPartition(arr, start, end, pivot);
      if (end - pivotNewIndex > 16) {
        stack.push([pivotNewIndex, end, depth - 1]);
      }
      if (pivotNewIndex - start > 16) {
        stack.push([start, pivotNewIndex, depth - 1]);
      }
    }
  }
  insertionSort(arr);
}

/**
 *
 * @param {number[]} arr
 * @param {number} start
 * @param {number} end
 */
function shellSortBound(arr, start, end) {
  let inc = Math.round((start + end) / 2);
  let i;
  let j;
  let t;

  while (inc >= start) {
    for (i = inc; i < end; i++) {
      t = arr[i];
      j = i;
      while (j >= inc && arr[j - inc] > t) {
        arr[j] = arr[j - inc];
        j -= inc;
      }
      arr[j] = t;
    }
    inc = Math.round(inc / 2.2);
  }
}

/**
 * Insertion sort
 * @param {number[]} arr
 */
function insertionSort(arr) {
  for (let i = 1, l = arr.length; i < l; i++) {
    const value = arr[i];
    let j;
    for (j = i - 1; j >= 0; j--) {
      if (arr[j] <= value) break;
      arr[j + 1] = arr[j];
    }
    arr[j + 1] = value;
  }
}

/**
 * In-place quick sort
 * @param {number[]} arr
 * @param {number} start
 * @param {number} end
 * @param {number} pivotIndex
 * @returns number
 */
function inplaceQuicksortPartition(arr, start, end, pivotIndex) {
  let i = start;
  let j = end;
  const pivot = arr[pivotIndex];
  const partition = true;
  while (partition) {
    while (arr[i] < pivot) {
      i++;
    }
    j--;
    while (pivot < arr[j]) {
      j--;
    }
    if (!(i < j)) {
      return i;
    }
    // swap(arr, i, j);
    const t = arr[i];
    arr[i] = arr[j];
    arr[j] = t;
    i++;
  }
  return i;
}
  
  function quickInsertionSort2(arr) {
  if (!arr || arr.length < 1) {
    return;
  }
  let startIndex = 0;
  let endIndex = arr.length - 1;
  let stackLength = 0;
  const startIndexes = [];
  const endIndexes = [];
  // variables for partitioning
  let _swap_temp;
  let left;
  let partitionIndex;
  let pivot;
  let right;
  // variables for insertion sort
  let i;
  let j;
  let key;
  do {
    // in my testing, I found 32 is very good choice for totally generated-random data,
    // more than 100 will cause slower speed overal.
    if (endIndex - startIndex <= 32) {
      // even using insertionSort,
      // still need this because it still come here !!
      if (endIndex - startIndex === 1) {
        if (arr[startIndex] > arr[endIndex]) {
          _swap_temp = arr[startIndex];
          arr[startIndex] = arr[endIndex];
          arr[endIndex] = _swap_temp;
        }
      } else {
        // start of insertion sort
        for (i = startIndex + 1; endIndex >= i; i++) {
          key = arr[i];
          // Move elements of arr[startIndex..i-1], that are
          // greater than key, to one position ahead
          // of their current position
          for (j = i - 1; j >= startIndex; j--) {
            if (arr[j] > key) {
              arr[j + 1] = arr[j];
              // eslint-disable-next-line no-continue
              continue;
            }
            // use 'break' to avoid decreasing 'j'
            break;
          }
          // swap
          arr[j + 1] = key;
        }
        // end of insertion sort
      }
      // continue to process next data, is there any data inside stack ?
      if (stackLength > 0) {
        // pop
        stackLength--; // reduce counter to get the last position from stack
        startIndex = startIndexes[stackLength];
        endIndex = endIndexes[stackLength];
      } else {
        // no data inside stack, so finish
        break;
      }
    } else {
      // squeeze every millisecond by put main logic here instead of separate function
      // start of partitioning
      // minimize worst case scenario
      // === start of select pivot ============
      pivot = arr[startIndex];
      // try to find a different element value
      j = endIndex;
      while (pivot === arr[j] && j >= startIndex) {
        j--;
      }
      if (j > startIndex) {
        // check which element is lower?
        // use the lower value as pivot
        if (pivot > arr[j]) {
          pivot = arr[j];
        }
      }
      // === end of select pivot ============
      left = startIndex;
      right = endIndex;
      do {
        while (pivot > arr[left]) {
          left++;
        }
        while (arr[right] > pivot) {
          right--;
        }
        if (left >= right) {
          partitionIndex = right;
          break;
        }
        // swap(left, right);
        // because many swaps, so optimize to implement swap here !
        _swap_temp = arr[left];
        arr[left] = arr[right];
        arr[right] = _swap_temp;
        left++;
        right--;
        // eslint-disable-next-line no-constant-condition
      } while (true); // loop forever until break
      if (partitionIndex > startIndex) {
        // has lower partition, so process it
        if (endIndex > partitionIndex + 1) {
          // push 'right' side partition info into stack for later
          startIndexes[stackLength] = partitionIndex + 1;
          endIndexes[stackLength] = endIndex;
          stackLength++; // increase counter for NEXT slot
        }
        // prepare next loop
        // keep same value for startIndex but update endIndex
        endIndex = partitionIndex;
      } else if (endIndex > partitionIndex + 1) {
        // at this point, it means there is no 'lower' side partition but has 'higher' side partition
        // prepare next loop
        // keep same value for endIndex but update startIndex
        startIndex = partitionIndex + 1;
      }
      // end of Tony Hoare partitioning
    }
  } while (endIndex > startIndex);
}
</script>

Script Preparation code:

var input = [];
for (var i = 0; i < 1000000; i++) {
  input[i] = Math.round(Math.random() * 1000000);
}

Tests:

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

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

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

Fastest: N/A

Slowest: N/A

ⓘ Get performance results from real users on your website with Request Metrics.

Website Performance Monitoring by Request Metrics

Latest run results:

Run details: (Test run date: 2 years ago)

User agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_7) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/94.0.4606.61 Safari/537.36

Browser/OS: Chrome 94 on Mac OS X 10.15.7

View result in a separate tab

Test name	Executions per second
Built-in Sort	8195.7 Ops/sec
Naive Quicksort	4982.1 Ops/sec
Inplace Quicksort	59092.8 Ops/sec
Heap Sort	30375.6 Ops/sec
Merge Sort	9890.0 Ops/sec
Shell Sort	13261.5 Ops/sec
Comb Sort	13544.7 Ops/sec
Insertion Sort	4548.0 Ops/sec
Fast QuickSort	83284.0 Ops/sec
mSort	17901.9 Ops/sec
Radix Bucket Sort	7690.7 Ops/sec
Bubble Sort	1477.4 Ops/sec
Quick Insertion Sort	76584.8 Ops/sec
QuickInsertionSort	76139.8 Ops/sec

Test Quick Insertion Sort3 (version: 2)

Port from jsperf(https://jsperf.com/sorting-algorithms/58)

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

Created: 2 years ago by: Registered User

Jump to the latest result

Built-in Sort

Naive Quicksort

Inplace Quicksort

Heap Sort

Merge Sort

Shell Sort

Comb Sort

Insertion Sort

Fast QuickSort

mSort

Radix Bucket Sort

Bubble Sort

Quick Insertion Sort

QuickInsertionSort

Suite status: <idle, ready to run>

Experimental features:

Fastest: N/A

Slowest: N/A