{"ScriptPreparationCode":"var input = [];\r\nfor (var i = 0; i \u003C 100; i\u002B\u002B) {\r\n input[i] = Math.round(Math.random() * 1000000);\r\n}\r\n\r\nfunction swap(ary, a, b) {\r\n var t = ary[a];\r\n ary[a] = ary[b];\r\n ary[b] = t;\r\n}\r\n\r\n// Built-in with comparison function (default sorting is \u0022dictionary-style\u0022)\r\nfunction builtin_sort(ary) {\r\n return ary.sort(function(a, b) {\r\n return a - b;\r\n });\r\n}\r\n\r\n// Bubble Sort\r\nfunction bubble_sort(ary) {\r\n var a, b;\r\n for (a = 0; a \u003C ary.length; a\u002B\u002B) {\r\n for (b = a \u002B 1; b \u003C ary.length; b\u002B\u002B) {\r\n if (ary[a] \u003E ary[b]) {\r\n swap(ary, a, b);\r\n }\r\n }\r\n }\r\n\r\n return ary;\r\n}\r\n//Insertion sort\r\nfunction insertion_sort(ary) {\r\n for (var i = 1, l = ary.length; i \u003C l; i\u002B\u002B) {\r\n var value = ary[i];\r\n for (var j = i - 1; j \u003E= 0; j--) {\r\n if (ary[j] \u003C= value) break;\r\n ary[j \u002B 1] = ary[j];\r\n }\r\n ary[j \u002B 1] = value;\r\n }\r\n return ary;\r\n}\r\n\r\n// Naive (but understandable) quicksort (memory hog)\r\nfunction naive_quicksort(ary) {\r\n if (ary.length \u003C= 1) {\r\n return ary;\r\n }\r\n\r\n var less = [],\r\n greater = [],\r\n pivot = ary.pop();\r\n\r\n for (var i = 0; i \u003C ary.length; i\u002B\u002B) {\r\n if (ary[i] \u003C pivot) {\r\n less.push(ary[i]);\r\n } else {\r\n greater.push(ary[i]);\r\n }\r\n }\r\n\r\n less = naive_quicksort(less);\r\n greater = naive_quicksort(greater);\r\n\r\n return less.concat(pivot, greater);\r\n}\r\n\r\n// In place quicksort\r\nfunction inplace_quicksort_partition(ary, start, end, pivotIndex) {\r\n var i = start,\r\n j = end;\r\n var pivot = ary[pivotIndex];\r\n\r\n while (true) {\r\n while (ary[i] \u003C pivot) {\r\n i\u002B\u002B;\r\n }\r\n j--;\r\n while (pivot \u003C ary[j]) {\r\n j--;\r\n }\r\n if (!(i \u003C j)) {\r\n return i;\r\n }\r\n swap(ary, i, j);\r\n i\u002B\u002B;\r\n }\r\n}\r\n\r\nfunction inplace_quicksort(ary, start, end) {\r\n if (start \u003C end - 1) {\r\n var pivotIndex = Math.round((start \u002B end) / 2);\r\n\r\n pivotIndex = inplace_quicksort_partition(ary, start, end, pivotIndex);\r\n\r\n inplace_quicksort(ary, start, pivotIndex - 1);\r\n inplace_quicksort(ary, pivotIndex \u002B 1, end);\r\n }\r\n\r\n return ary;\r\n}\r\n\r\n// Heap sort\r\nfunction heapSort(ary) {\r\n heapify(ary);\r\n\r\n for (var end = ary.length - 1; end \u003E 0; end--) {\r\n swap(ary, end, 0);\r\n shiftDown(ary, 0, end - 1);\r\n }\r\n\r\n return ary;\r\n}\r\n\r\nfunction heapify(ary) {\r\n for (var start = (ary.length \u003E\u003E 1) - 1; start \u003E= 0; start--) {\r\n shiftDown(ary, start, ary.length - 1);\r\n }\r\n}\r\n\r\nfunction shiftDown(ary, start, end) {\r\n var root = start,\r\n child,\r\n s;\r\n\r\n while (root * 2 \u002B 1 \u003C= end) {\r\n child = root * 2 \u002B 1;\r\n s = root;\r\n\r\n if (ary[s] \u003C ary[child]) {\r\n s = child;\r\n }\r\n\r\n if (child \u002B 1 \u003C= end \u0026\u0026 ary[s] \u003C ary[child \u002B 1]) {\r\n s = child \u002B 1;\r\n }\r\n\r\n if (s !== root) {\r\n swap(ary, root, s);\r\n root = s;\r\n } else {\r\n return;\r\n }\r\n }\r\n}\r\n\r\n// Merge sort\r\nfunction merge_sort(ary) {\r\n if (ary.length \u003C= 1) {\r\n return ary;\r\n }\r\n\r\n var m = ary.length \u003E\u003E 1;\r\n\r\n var left = ary.slice(0, m),\r\n right = ary.slice(m);\r\n\r\n return merge(merge_sort(left), merge_sort(right));\r\n}\r\n\r\nfunction merge(left, right) {\r\n var result = [],\r\n li = 0,\r\n ri = 0;\r\n\r\n while (li \u003C left.length || ri \u003C right.length) {\r\n if (li \u003C left.length \u0026\u0026 ri \u003C right.length) {\r\n if (left[li] \u003C= right[ri]) {\r\n result.push(left[li]);\r\n li\u002B\u002B;\r\n } else {\r\n result.push(right[ri]);\r\n ri\u002B\u002B;\r\n }\r\n } else if (li \u003C left.length) {\r\n result.push(left[li]);\r\n li\u002B\u002B;\r\n } else if (ri \u003C right.length) {\r\n result.push(right[ri]);\r\n ri\u002B\u002B;\r\n }\r\n }\r\n\r\n return result;\r\n}\r\n\r\n// Shell sort\r\nfunction shell_sort(ary) {\r\n var inc = Math.round(ary.length / 2),\r\n i,\r\n j,\r\n t;\r\n\r\n while (inc \u003E 0) {\r\n for (i = inc; i \u003C ary.length; i\u002B\u002B) {\r\n t = ary[i];\r\n j = i;\r\n while (j \u003E= inc \u0026\u0026 ary[j - inc] \u003E t) {\r\n ary[j] = ary[j - inc];\r\n j -= inc;\r\n }\r\n ary[j] = t;\r\n }\r\n inc = Math.round(inc / 2.2);\r\n }\r\n\r\n return ary;\r\n}\r\n//Comb Sort (Basically bubblesort with a small modification, but heaps faster)\r\nfunction comb_sort(ary) {\r\n var gap = ary.length;\r\n while (true) {\r\n gap = newgap(gap);\r\n var swapped = false;\r\n for (var i = 0, l = ary.length; i \u003C l; i\u002B\u002B) {\r\n var j = i \u002B gap;\r\n if (ary[i] \u003C ary[j]) {\r\n swap(ary, i, j);\r\n swapped = true;\r\n }\r\n }\r\n if (gap == 1 \u0026\u0026 !swapped) break;\r\n }\r\n return ary;\r\n}\r\nfunction newgap(gap) {\r\n gap = ((gap * 10) / 13) | 0;\r\n if (gap == 9 || gap == 10) gap = 11;\r\n if (gap \u003C 1) gap = 1;\r\n return gap;\r\n}\r\n//faster quicksort using a stack to eliminate recursion, sorting inplace to reduce memory usage, and using insertion sort for small partition sizes\r\nfunction fast_quicksort(ary) {\r\n var stack = [];\r\n var entry = [\r\n 0,\r\n ary.length,\r\n 2 * Math.floor(Math.log(ary.length) / Math.log(2))\r\n ];\r\n stack.push(entry);\r\n while (stack.length \u003E 0) {\r\n entry = stack.pop();\r\n var start = entry[0];\r\n var end = entry[1];\r\n var depth = entry[2];\r\n if (depth == 0) {\r\n ary = shell_sort_bound(ary, start, end);\r\n continue;\r\n }\r\n depth--;\r\n var pivot = Math.round((start \u002B end) / 2);\r\n\r\n var pivotNewIndex = inplace_quicksort_partition(ary, start, end, pivot);\r\n if (end - pivotNewIndex \u003E 16) {\r\n entry = [pivotNewIndex, end, depth];\r\n stack.push(entry);\r\n }\r\n if (pivotNewIndex - start \u003E 16) {\r\n entry = [start, pivotNewIndex, depth];\r\n stack.push(entry);\r\n }\r\n }\r\n ary = insertion_sort(ary);\r\n return ary;\r\n}\r\nfunction shell_sort_bound(ary, start, end) {\r\n var inc = Math.round((start \u002B end) / 2),\r\n i,\r\n j,\r\n t;\r\n\r\n while (inc \u003E= start) {\r\n for (i = inc; i \u003C end; i\u002B\u002B) {\r\n t = ary[i];\r\n j = i;\r\n while (j \u003E= inc \u0026\u0026 ary[j - inc] \u003E t) {\r\n ary[j] = ary[j - inc];\r\n j -= inc;\r\n }\r\n ary[j] = t;\r\n }\r\n inc = Math.round(inc / 2.2);\r\n }\r\n\r\n return ary;\r\n}\r\n\r\nfunction mSort(list) {\r\n if (list.length \u003C 14) {\r\n return insertion_sort(list);\r\n }\r\n\r\n var half = Math.floor(list.length / 2);\r\n var a = mSort(list.slice(0, half));\r\n var b = mSort(list.slice(half, list.length));\r\n var aCount = 0;\r\n var bCount = 0;\r\n var returnList = [];\r\n\r\n while (true) {\r\n if (a[aCount] \u003C= b[bCount]) {\r\n returnList.push(a[aCount]);\r\n aCount\u002B\u002B;\r\n if (aCount === a.length) {\r\n returnList = returnList.concat(b.slice(bCount, b.length));\r\n break;\r\n }\r\n } else {\r\n returnList.push(b[bCount]);\r\n bCount\u002B\u002B;\r\n if (bCount === b.length) {\r\n returnList = returnList.concat(a.slice(aCount, a.length));\r\n break;\r\n }\r\n }\r\n }\r\n return returnList;\r\n}\r\n\r\nfunction bubbleSort(items) {\r\n var length = items.length;\r\n for (var i = 0; i \u003C length; i\u002B\u002B) {\r\n //Number of passes\r\n for (var j = 0; j \u003C length - i - 1; j\u002B\u002B) {\r\n //Notice that j \u003C (length - i)\r\n //Compare the adjacent positions\r\n if (items[j] \u003E items[j \u002B 1]) {\r\n //Swap the numbers\r\n var tmp = items[j]; //Temporary variable to hold the current number\r\n items[j] = items[j \u002B 1]; //Replace current number with adjacent number\r\n items[j \u002B 1] = tmp; //Replace adjacent number with current number\r\n }\r\n }\r\n }\r\n}\r\n\r\nfunction radixBucketSort(arr) {\r\n var idx1, idx2, idx3, len1, len2, radix, radixKey;\r\n var radices = {},\r\n buckets = {},\r\n num,\r\n curr;\r\n var currLen, radixStr, currBucket;\r\n\r\n len1 = arr.length;\r\n len2 = 10; // radix sort uses ten buckets\r\n\r\n // find the relevant radices to process for efficiency\r\n for (idx1 = 0; idx1 \u003C len1; idx1\u002B\u002B) {\r\n radices[arr[idx1].toString().length] = 0;\r\n }\r\n\r\n // loop for each radix. For each radix we put all the items\r\n // in buckets, and then pull them out of the buckets.\r\n for (radix in radices) {\r\n // put each array item in a bucket based on its radix value\r\n len1 = arr.length;\r\n for (idx1 = 0; idx1 \u003C len1; idx1\u002B\u002B) {\r\n curr = arr[idx1];\r\n // item length is used to find its current radix value\r\n currLen = curr.toString().length;\r\n // only put the item in a radix bucket if the item\r\n // key is as long as the radix\r\n if (currLen \u003E= radix) {\r\n // radix starts from beginning of key, so need to\r\n // adjust to get redix values from start of stringified key\r\n radixKey = curr.toString()[currLen - radix];\r\n // create the bucket if it does not already exist\r\n if (!buckets.hasOwnProperty(radixKey)) {\r\n buckets[radixKey] = [];\r\n }\r\n // put the array value in the bucket\r\n buckets[radixKey].push(curr);\r\n } else {\r\n if (!buckets.hasOwnProperty(\u00220\u0022)) {\r\n buckets[\u00220\u0022] = [];\r\n }\r\n buckets[\u00220\u0022].push(curr);\r\n }\r\n }\r\n // for current radix, items are in buckets, now put them\r\n // back in the array based on their buckets\r\n // this index moves us through the array as we insert items\r\n idx1 = 0;\r\n // go through all the buckets\r\n for (idx2 = 0; idx2 \u003C len2; idx2\u002B\u002B) {\r\n // only process buckets with items\r\n if (buckets[idx2] != null) {\r\n currBucket = buckets[idx2];\r\n // insert all bucket items into array\r\n len1 = currBucket.length;\r\n for (idx3 = 0; idx3 \u003C len1; idx3\u002B\u002B) {\r\n arr[idx1\u002B\u002B] = currBucket[idx3];\r\n }\r\n }\r\n }\r\n buckets = {};\r\n }\r\n}\r\n","TestCases":[{"Name":"Inplace Quicksort","Code":"inplace_quicksort(input.slice(0), 0, input.length);","IsDeferred":false},{"Name":"Merge Sort","Code":"merge_sort(input.slice(0));","IsDeferred":false},{"Name":"Built-in Sort","Code":"builtin_sort(input.slice(0));","IsDeferred":false},{"Name":"Heap Sort","Code":"heapSort(input.slice(0));","IsDeferred":false},{"Name":"Shell Sort","Code":"shell_sort(input.slice(0));","IsDeferred":false},{"Name":"Insertion Sort","Code":"insertion_sort(input.slice(0));","IsDeferred":false},{"Name":"mSort","Code":"mSort(input.slice(0));","IsDeferred":false},{"Name":"Comb Sort","Code":"comb_sort(input.slice(0));","IsDeferred":false},{"Name":"Radix Bucket Sort","Code":"radixBucketSort(input.slice(0));","IsDeferred":false},{"Name":"Fast QuickSort","Code":"fast_quicksort(input.slice(0));","IsDeferred":false},{"Name":"Naive Quicksort","Code":"naive_quicksort(input.slice(0));","IsDeferred":false},{"Name":"Bubble Sort","Code":"bubbleSort(input.slice(0));","IsDeferred":false}]}