Test case details

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__func(a, b) {return a - b;};   function builtin_sort(ary) {       return ary.sort(builtin_sort__func);   }     // 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 //It should NOT be running at the EXACT same speed as the inplace version due to the number of changes, but it does on jsPerf for some reason.... 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;   } </script>
var input = [];     for (var i = 0; i < 1000; i++) {       input[i] = Math.round(Math.random() * 1000000);     }

Test cases

Test #1

builtin_sort(input.slice(0));

Test #2

bubble_sort(input.slice(0));

Test #3

naive_quicksort(input.slice(0));

Test #4

inplace_quicksort(input.slice(0), 0, input.length);

Test #5

heapSort(input.slice(0));

Test #6

merge_sort(input.slice(0));

Test #7

shell_sort(input.slice(0));

Test #8

comb_sort(input.slice(0));

Test #9

insertion_sort(input.slice(0));

Test #10

fast_quicksort(input.slice(0));