{"ScriptPreparationCode":"var input = [];\r\nfor (var i = 0; i \u003C 1000; i\u002B\u002B) {\r\n input[i] = Math.round(Math.random() * 1000000);\r\n}","TestCases":[{"Name":"built in sort","Code":"input.slice(0).sort(function(a, b) {\r\n return a - b;\r\n});","IsDeferred":false},{"Name":"custom sort","Code":"\r\nfunction fast_quicksort(ary) {\r\n var stack = [];\r\n var entry = [0, ary.length, 2 * Math.floor(Math.log(ary.length) / Math.log(2))];\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, j, 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\nfunction inplace_quicksort_partition(ary, start, end, pivotIndex) {\r\n var i = start, j = end;\r\n var pivot = ary[pivotIndex];\r\n \r\n while(true) {\r\n while(ary[i] \u003C pivot) {i\u002B\u002B};\r\n j--;\r\n while(pivot \u003C ary[j]) {j--};\r\n if(!(i\u003Cj)) {\r\n return i;\r\n }\r\n swap(ary,i,j);\r\n i\u002B\u002B;\r\n }\r\n}\r\nfunction insertion_sort(ary) {\r\n for(var i=1,l=ary.length;i\u003Cl;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)\r\n break;\r\n ary[j\u002B1] = ary[j];\r\n }\r\n ary[j\u002B1] = value;\r\n }\r\n return ary;\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\nfast_quicksort(input.slice(0));","IsDeferred":false}]}