Run results for: Javascript native sort vs quick-insertion-sort

Run details:

User agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:50.0) Gecko/20100101 Firefox/50.0

Browser: Firefox 50

Operating system: Windows

Device Platform: Desktop

Date tested: 7 months ago

Test name	Executions per second
Built-in Sort	3.8 Ops/sec
Naive Quicksort	1.8 Ops/sec
Inplace Quicksort	11.6 Ops/sec
Fast QuickSort	11.1 Ops/sec
QuickInsertionSort	1.0 Ops/sec

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
      }
    }        
  }
}
  
  function quickInsertionSort(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);
}
  
  // 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 = {};
    }
  }
</script>

Script Preparation code:

var input = [];
for (var i = 0; i < 1000000; i++) {
  input[i] = 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);
Fast QuickSort
fast_quicksort(input.slice(0));
QuickInsertionSort
quickInsertionSort(input.slice(0));

Run results for: Javascript native sort vs quick-insertion-sort

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

Built-in Sort

Naive Quicksort

Inplace Quicksort

Fast QuickSort

QuickInsertionSort