<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>