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 = {};

  }

}

​