2b:null 2c:["$","title",null,{"children":"Beating the built-in sort, sometimes | Job van der Zwan | Observable"}] 31:Td6c,time_sort = { const shift = 32 - inputWidth; const partialShuffle = (arr, n) => { for(let i = 0; i < n; i++) { const j = arr.length - 1 - (Math.random() * (arr.length/2) | 0); const t = arr[j]; arr[j] = arr[arr.length - 1 - i]; arr[arr.length - 1 - i] = t; } }; const float = arrayType === "Array(float)" || arrayType === "Float32Array" || arrayType === "Float64Array"; const randomize = partial_checkbox ? (n = 10) => { for (const input of testInputs) partialShuffle(input, n); } : () => { for (const input of testInputs) { randomValues(input, {shift, logDistributed: false, float}); } }; // start out sorted for (const input of testInputs) input.sort((a, b) => a - b); const sorts = [ quickSortNR, // quickSortNR2, leapfrogSort, leapfrogSort2, leapfrogSort3, leapfrogSortPrimes, leapfrogSortPrimes2, leapfrogSortPrimes3, // leapfrog4Sort, // leapfrog3Sort, // leapfrog4Sort2 ]; const timings = { radix: [], quicksort: [], quickSortNR: [], quickSortNR2: [], leapfrogSort: [], leapfrogSort2: [], leapfrogSort3: [], leapfrogSortPrimes: [], leapfrogSortPrimes2: [], leapfrogSortPrimes3: [], leapfrog4Sort: [], leapfrog3Sort: [], leapfrog4Sort2: [], leapfrog4Sort2b: [], insertionSort: [], insertionSort2: [], native: [], testInputs }; if (time_sort_checkbox){ let t0 = 0, t1 = 0, maxTiming = 0; const runs = 10; for (let i = 0; i < runs && maxTiming < 5000; i++) { if (testInputs[0].length <= 256) { randomize(); t0 = performance.now(); for (const input of testInputs) insertionSort(input); t1 = performance.now(); t1 -= t0; timings.insertionSort.push(t1); if (t1 > maxTiming) { maxTiming = t1; } randomize(); t0 = performance.now(); for (const input of testInputs) insertionSort2(input); t1 = performance.now(); t1 -= t0; timings.insertionSort2.push(t1); if (t1 > maxTiming) { maxTiming = t1; } } randomize(); if (arrayType === "Uint8Array") { t0 = performance.now(); for (const input of testInputs) radixsortU8(input, 0, input.length); t1 = performance.now(); } else { t0 = performance.now(); for (const input of testInputs) radixsort(input); t1 = performance.now(); } t1 -= t0; timings.radix.push(t1); if (t1 > maxTiming) { maxTiming = t1; } randomize(); if (Array.isArray(testInputs[0])) { t0 = performance.now(); for (const input of testInputs) input.sort((a, b) => a - b); t1 = performance.now(); } else { t0 = performance.now(); for (const input of testInputs) input.sort(); t1 = performance.now(); } t1 -= t0; timings.native.push(t1); if (t1 > maxTiming) { maxTiming = t1; } for (const sort of sorts) { randomize(); t0 = performance.now(); for (const input of testInputs) sort(input); t1 = performance.now(); t1 -= t0; timings[sort.name].push(t1); if (t1 > maxTiming) { maxTiming = t1; } } yield timings; } } yield timings; } 32:T62a,function leapfrogSort(arr) { // golden ratio = (1 + 5 ** 0.5) / 2 = 1.618033988749895 // 1 / golden ratio = 0.6180339887498948 const invGR = 2/(1 + Math.sqrt(5)); const {length} = arr; const {SQRT1_2, SQRT2} = Math; let p = length * 0.5 / invGR, q = p * SQRT1_2, i, j, k, a, b, c; do { p *= invGR; q *= invGR; if (p - q < 2.0) p *= SQRT2; i = 0; j = (p-q | 0); k = (p | 0); for (;k < length; i++, j++, k++) { // three-way comparison a = arr[i]; b = arr[j]; c = arr[k]; if (a < b) { if (b < c) { // a < b < c continue; } if (c < a) { // c < a < b arr[i] = c; arr[j] = a; arr[k] = b; continue; } else { // a < c < b arr[j] = c; arr[k] = b; continue; } } else { if (c < b) { // c < b < a arr[i] = c; arr[j] = b; arr[k] = a; continue; } else if (c < a) { // b < c < a arr[i] = b; arr[j] = c; arr[k] = a; continue; } else { // b < a < c arr[i] = b; arr[j] = a; continue; } } } } while ((q|0) > 1); // last insertion sort pass as final fixup for (i = 1; i < length; i++) { a = arr[i]; j = i; if ((b = arr[j-1]) > a) { do { arr[j] = b; } while (--j > 0 && (b = arr[j-1]) > a); arr[j] = a; } } return arr; }33:T433,function leapfrogSort2(arr) { // golden ratio = (1 + 5 ** 0.5) / 2 = 1.618033988749895 // 1 / golden ratio = 0.6180339887498948 const invGR = 2/(1 + Math.sqrt(5)); const {length} = arr; const {SQRT1_2, SQRT2} = Math; let p = length / 2, q = p * SQRT1_2, i, j, k, a, b, c; do { i = 0; j = (q|0); k = (p+q|0); for (;k < length; i++, j++, k++) { // three-way comparison a = arr[i]; b = arr[j]; if (b < a) { arr[i] = c = b; arr[j] = b = a; a = c; } c = arr[k]; if (c < b) { arr[k] = b; if (c > a) { arr[j] = c; } else { arr[i] = c; arr[j] = a; } } } p *= invGR; q *= invGR; if (p - q < 2.0) p *= SQRT2; } while ((q|0) > 1); // last insertion sort pass as final fixup for (i = 1; i < length; i++) { a = arr[i]; j = i; if ((b = arr[j-1]) > a) { do { arr[j] = b; } while (--j > 0 && (b = arr[j-1]) > a); arr[j] = a; } } return arr; }34:Tb5b,function leapfrogSort3(arr) { // golden ratio = (1 + 5 ** 0.5) / 2 = 1.618033988749895 // 1 / golden ratio = 0.6180339887498948 const invRatio = // 2 / (1 + 5 ** 0.5); // 1 / golden mean // 1 / 1.839286755214161; // tribonacci, https://oeis.org/A000073 // 1 / 1.927561975482925; // tetranacci, https://oeis.org/A000078 1 / 1.991964196605035; // heptanaci, https://en.wikipedia.org/wiki/Generalizations_of_Fibonacci_numbers#Higher_orders const {length} = arr; const {SQRT1_2, SQRT2} = Math; let gap1 = length / 2, gap2 = gap1 * Math.SQRT1_2, a, b, c, i, j, k; while (gap1 - gap2 >= 2) { i = 0; j = gap2 | 0; k = gap1 + gap2 | 0; for (;k < length;i++,j++,k++) { // three-way comparison a = arr[i]; b = arr[j]; c = arr[k]; if (a < b) { if (b < c) { // a < b < c continue; } if (c < a) { // c < a < b arr[i] = c; arr[j] = a; arr[k] = b; continue; } else { // a < c < b arr[j] = c; arr[k] = b; continue; } } else { if (c < b) { // c < b < a arr[i] = c; arr[j] = b; arr[k] = a; continue; } else if (c < a) { // b < c < a arr[i] = b; arr[j] = c; arr[k] = a; continue; } else { // b < a < c arr[i] = b; arr[j] = a; continue; } } } gap1 *= invRatio; gap2 *= invRatio; // descending pass if (gap1 - gap2 < 2) break; i = length - 1 - gap1 - gap2 | 0; j = length - 1 - gap2 | 0; k = length - 1; for (;i >= 0;i--,j--,k--) { // three-way comparison a = arr[i]; b = arr[j]; c = arr[k]; if (a < b) { if (b < c) { // a < b < c continue; } if (c < a) { // c < a < b arr[i] = c; arr[j] = a; arr[k] = b; continue; } else { // a < c < b arr[j] = c; arr[k] = b; continue; } } else { if (c < b) { // c < b < a arr[i] = c; arr[j] = b; arr[k] = a; continue; } else if (c < a) { // b < c < a arr[i] = b; arr[j] = c; arr[k] = a; continue; } else { // b < a < c arr[i] = b; arr[j] = a; continue; } } } gap1 *= invRatio; gap2 *= invRatio; } // last insertion sort pass as final fixup for (i = 1; i < length; i++) { a = arr[i]; j = i; if ((b = arr[j-1]) > a) { do { arr[j] = b; } while (--j > 0 && (b = arr[j-1]) > a); arr[j] = a; } } return arr; }35:Tb3d,leapfrogSortPrimes = { // most recent set of (pseudo)primes // k = p + q; // j = q; const ps = Uint32Array.from([3, 5, 7, 10, 13, 17, 22, 29, 37, 51, 65, 83, 106, 137, 177, 226, 291, 371, 473, 607, 773, 985, 1253, 1594, 2029, 2581, 3287, 4183, 5321, 6769, 8611, 10954, 13934, 17726, 22549, 28685, 36489, 46415, 59043, 75109, 95541, 121531, 154591, 196643, 250139, 318187, 404741, 514841, 654889, 833033, 1059635, 1347877, 1714529, 2180918, 2774171, 3528803, 4488709, 5709731, 7262891, 9238543, 11751609, 14948281, 19014509, 24186831, 30766126, 39135119, 49780649, 63321967]), qs = Uint32Array.from([2, 3, 3, 7, 10, 11, 15, 19, 26, 35, 46, 58, 74, 95, 123, 159, 205, 262, 334, 427, 545, 695, 886, 1126, 1433, 1823, 2323, 2957, 3761, 4786, 6087, 7745, 9851, 12533, 15943, 20283, 25801, 32819, 41749, 53111, 67559, 85934, 109313, 139047, 176873, 224993, 286193, 364047, 463079, 589045, 749278, 953093, 1212353, 1542139, 1961633, 2495239, 3173993, 4037389, 5135639, 6532637, 8309641, 10570029, 13445287, 17102671, 21754937, 27672709, 35200237, 44775391]); return function leapfrogSortPrimes(arr) { const length = arr.length; let depth = 1; while (++depth < ps.length && (ps[depth]+qs[depth]) < length/2) {} // additional increase because we decrement by 2 instead of 1 depth++; let p, q, a, b, c, i, j, k; outer: while ((depth -= 2) >= 0) { p = ps[depth]; q = qs[depth]; i = 0; j = 0; k = p; while (k < p+q) { // two-way comparison a = arr[j++]; b = arr[k++]; if (a < b) continue; arr[j-1] = b; arr[k-1] = a; } while (k < length) { // three-way comparison a = arr[i]; b = arr[j]; c = arr[k]; if (a < b) { if (c < a) { // c < a < b arr[i] = c; arr[j] = a; arr[k] = b; } else if (c < b) { // a < c < b arr[j] = c; arr[k] = b; } else { // a < b < c } } else { if (c < b) { // c < b < a arr[i] = c; arr[j] = b; arr[k] = a; } else if (c < a) { // b < c < a arr[i] = b; arr[j] = c; arr[k] = a; } else { // b < a < c arr[i] = b; arr[j] = a; } } i++; j++; k++; } } // Final insertion sort pass to // fix any items still out of place for (i = 1; i < length; i++) { a = arr[i]; j = i; // modified to exploit the // expected distribution. if ((b = arr[j-1]) > a) { do { arr[j] = b; } while (--j > 0 && (b = arr[j-1]) > a); arr[j] = a; } } return arr; } }36:Tef1,leapfrogSortPrimes2 = { // most recent set of (pseudo)primes // k = p + q; // j = q; const ps = Uint32Array.from([3, 5, 7, 10, 13, 17, 22, 29, 37, 51, 65, 83, 106, 137, 177, 226, 291, 371, 473, 607, 773, 985, 1253, 1594, 2029, 2581, 3287, 4183, 5321, 6769, 8611, 10954, 13934, 17726, 22549, 28685, 36489, 46415, 59043, 75109, 95541, 121531, 154591, 196643, 250139, 318187, 404741, 514841, 654889, 833033, 1059635, 1347877, 1714529, 2180918, 2774171, 3528803, 4488709, 5709731, 7262891, 9238543, 11751609, 14948281, 19014509, 24186831, 30766126, 39135119, 49780649, 63321967]), qs = Uint32Array.from([2, 3, 3, 7, 10, 11, 15, 19, 26, 35, 46, 58, 74, 95, 123, 159, 205, 262, 334, 427, 545, 695, 886, 1126, 1433, 1823, 2323, 2957, 3761, 4786, 6087, 7745, 9851, 12533, 15943, 20283, 25801, 32819, 41749, 53111, 67559, 85934, 109313, 139047, 176873, 224993, 286193, 364047, 463079, 589045, 749278, 953093, 1212353, 1542139, 1961633, 2495239, 3173993, 4037389, 5135639, 6532637, 8309641, 10570029, 13445287, 17102671, 21754937, 27672709, 35200237, 44775391]); // const ps = Uint32Array.from([3, 5, 7, 10, 13, 17, 22, 29, 37, 46, 57, 71, 89, 111, 137, 173, 213, 262, 319, 389, 473, 577, 699, 849, 1027, 1241, 1497, 1803, 2167, 2602, 3121, 3739, 4474, 5345, 6379, 7603, 9053, 10763, 12781, 15161, 17961, 21254, 25121, 29657, 34973, 41197, 48469, 56963, 66877, 78513, 92177, 108217, 127047, 149153, 175106, 205573, 241341, 283331, 332627, 390503, 458446, 538217, 631859, 741794, 870869, 1022389, 1200271, 1409101, 1654265, 1942089, 2279986, 2676673, 3142378, 3689107, 4330957, 5084479, 5969105, 7007641, 8226869, 9658231, 11338631, 13311383, 15627371, 18346301, 21538283, 25285627, 29684947, 34849687, 40913011, 48031265, 56387986, 66198653]), // qs = Uint32Array.from([2, 3, 3, 3, 3, 3, 5, 7, 11, 13, 17, 19, 23, 31, 41, 47, 61, 73, 89, 113, 137, 167, 199, 251, 293, 359, 439, 523, 631, 761, 911, 1093, 1307, 1567, 1867, 2221, 2647, 3163, 3739, 4441, 5261, 6221, 7351, 8689, 10243, 12071, 14197, 16691, 19583, 22993, 26993, 31699, 37217, 43691, 51287, 60209, 70687, 82981, 97423, 114377, 134269, 157639, 185069, 217271, 255071, 299447, 351551, 412717, 484531, 568823, 667801, 783953, 920377, 1080523, 1268479, 1489207, 1748291, 2052493, 2409593, 2828809, 3321037, 3898841, 4577149, 5373499, 6308429, 7405997, 8694527, 10207229, 11983157, 14068031, 16515647, 19389133]); return function leapfrogSortPrimes2(arr) { const length = arr.length; let depth = 1; while (++depth < ps.length && ps[depth] < length*0.5) {} // additional increase because we decrement by 3 instead of 1 depth+=1; let i, j, k, a, b, c, p, q; while ((depth-=2) >= 0) { q = qs[depth], p = ps[depth]; i = 0, j = 0, k = p; for(;j < q && k < length; j++, k++) { a = arr[j]; b = arr[k]; if (a < b) continue; arr[j] = b; arr[k] = a; } for (;k < length; i++, j++, k++) { a = arr[i]; b = arr[j]; if (a > b) { arr[j] = c = a; arr[i] = a = b; b = c; } c = arr[k]; if (b <= c) continue; arr[k] = b; if (c > a) { arr[j] = c; } else { arr[j] = a; arr[i] = c; } } for(;j < length; i++, j++) { a = arr[i]; b = arr[j]; if (a < b) continue; arr[i] = b; arr[j] = a; } } // Final insertion sort pass to // fix any items still out of place // (can be modified to exploit the // expected distribution). for (i = 1; i < length; i++) { a = arr[j = i]; if ((b = arr[j-1]) > a) { do { arr[j] = b; } while (--j > 0 && (b = arr[j-1]) > a); arr[j] = a; } } return arr; }; }37:T1022,leapfrogSortPrimes3 = { // most recent set of (pseudo)primes // k = p + q; // j = q; const ps = Uint32Array.from([3, 5, 7, 10, 13, 17, 22, 29, 37, 51, 65, 83, 106, 137, 177, 226, 291, 371, 473, 607, 773, 985, 1253, 1594, 2029, 2581, 3287, 4183, 5321, 6769, 8611, 10954, 13934, 17726, 22549, 28685, 36489, 46415, 59043, 75109, 95541, 121531, 154591, 196643, 250139, 318187, 404741, 514841, 654889, 833033, 1059635, 1347877, 1714529, 2180918, 2774171, 3528803, 4488709, 5709731, 7262891, 9238543, 11751609, 14948281, 19014509, 24186831, 30766126, 39135119, 49780649, 63321967]), qs = Uint32Array.from([2, 3, 3, 7, 10, 11, 15, 19, 26, 35, 46, 58, 74, 95, 123, 159, 205, 262, 334, 427, 545, 695, 886, 1126, 1433, 1823, 2323, 2957, 3761, 4786, 6087, 7745, 9851, 12533, 15943, 20283, 25801, 32819, 41749, 53111, 67559, 85934, 109313, 139047, 176873, 224993, 286193, 364047, 463079, 589045, 749278, 953093, 1212353, 1542139, 1961633, 2495239, 3173993, 4037389, 5135639, 6532637, 8309641, 10570029, 13445287, 17102671, 21754937, 27672709, 35200237, 44775391]); return function leapfrogSortPrimes3(arr) { const length = arr.length; let depth = 1; while (++depth < ps.length && (ps[depth]+qs[depth]) < length/2) {} // additional increase because we decrement by 2 instead of 1 depth++; let p, q, a, b, c, i, j, k, noASwaps = 0, notSorted = true; outer: while ((depth -= 2) >= 0 && notSorted) { p = ps[depth]; q = qs[depth]; i = 0; j = 0; k = p; while (k < p+q) { // two-way comparison a = arr[j++]; b = arr[k++]; if (a < b) continue; arr[j-1] = b; arr[k-1] = a; } while (k < length) { // three-way comparison a = arr[i]; b = arr[j]; c = arr[k]; if (a < b) { if (c < a) { // c < a < b arr[i] = c; arr[j] = a; arr[k] = b; } else if (c < b) { // a < c < b arr[j] = c; arr[k] = b; } else { // a < b < c } } else { if (c < b) { // c < b < a arr[i] = c; arr[j] = b; arr[k] = a; } else if (c < a) { // b < c < a arr[i] = b; arr[j] = c; arr[k] = a; } else { // b < a < c arr[i] = b; arr[j] = a; } } i++; j++; k++; } // descending pass if ((depth -=2) < 0) break; p = ps[depth]; q = qs[depth]; i = length - 1 - p; j = length - 1; k = length - 1; while (i > length - 1 - p - q) { // two-way comparison a = arr[i--]; b = arr[j--]; if (a < b) continue; arr[i+1] = b; arr[j+1] = a; } while (i >= 0) { // three-way comparison a = arr[i]; b = arr[j]; c = arr[k]; if (a < b) { if (c < a) { // c < a < b arr[i] = c; arr[j] = a; arr[k] = b; } else if (c < b) { // a < c < b arr[j] = c; arr[k] = b; } else { // a < b < c } } else { if (c < b) { // c < b < a arr[i] = c; arr[j] = b; arr[k] = a; } else if (c < a) { // b < c < a arr[i] = b; arr[j] = c; arr[k] = a; } else { // b < a < c arr[i] = b; arr[j] = a; } } i--; j--; k--; } } // Final insertion sort pass to // fix any items still out of place for (i = 1; i < length; i++) { a = arr[i]; j = i; // modified to exploit the // expected distribution. if ((b = arr[j-1]) > a) { do { arr[j] = b; } while (--j > 0 && (b = arr[j-1]) > a); arr[j] = a; } } return arr; } }38:T457,function leapfrog3Sort(arr) { const length = arr.length; const invφ = (2 / (1 + 5 ** 0.5)); // const invφ = (1 + 5 ** 0.5)/6; let gap = length * invφ | 0; while (gap > 3) { let a = arr[0], b = 0, t0 = 0, t1 = 0, i = 1, j = i + gap; while (j < length) { t0 = arr[i]; if (a > t0) { b = a; a = t0; } else { b = t0; } // a, b are now sorted, insertion-sort // the leading value t1 = arr[j]; if (b > t1) { arr[j] = b; if (a > t1) { arr[i-1] = t1; } else { arr[i-1] = a; a = t1; } } i++; j++; } // last-iteration fix-up arr[i-1] = a; gap = gap * invφ | 0; } // Final insertion sort pass to // fix any items still out of place // (can be modified to exploit the // expected distribution). for (let i = 1; i < length; i++) { let b = arr[i], j; for ( j = i - 1; j >= 0 && arr[j] > b; j-- ) { arr[j+1] = arr[j]; } if (++j < i) { arr[j] = b; } } return arr; }39:Ta7a,function leapfrog4Sort2(arr) { const {length} = arr; let PHI = (1 + 5 ** 0.5) / 2, // = 1.618033988749895 shrinkfactor = 0.5, //PHI / 3, p = length * PHI / 2, q = p * 2 / (1 + 5**0.5), // r = p * (1 - Math.SQRT1_2), // / (3 + 5**0.5), p0 = p | 0, q0 = q | 0, r0 = r | 0; while (q0 > 1) { p0 = (p *= shrinkfactor) | 1; q0 = ((q *= shrinkfactor) | 1) - 2; r0 = ((r *= shrinkfactor) | 1) - 2; let i = 0, j = 0, k = 0, l = p0; for (; l < p0 + q0 || q0 <= 0 && l < length; k++, l++) { // two way comparison if (arr[k] < arr[l]) continue; const b = arr[k]; const a = arr[l]; arr[k] = a; arr[l] = b; } for (; l < p0 + q0 + r0 || r0 <= 0 && l < length; j++, k++, l++) { // three way comparison const a = arr[j]; const b = arr[k]; const c = arr[l]; if (a < b) { if (b < c) { // a < b < c continue; } if (c < a) { // c < a < b arr[j] = c; arr[k] = a; arr[l] = b; continue; } else { // a < c < b arr[k] = c; arr[l] = b; continue; } } else { if (c < b) { // c < b < a arr[j] = c; arr[k] = b; arr[l] = a; continue; } else if (c < a) { // b < c < a arr[j] = b; arr[k] = c; arr[l] = a; continue; } else { // b < a < c arr[j] = b; arr[k] = a; continue; } } } for (let a, at, b, bt, c, ct, d, dt; l < length; i++, j++, k++, l++) { // four way comparison, see // https://bertdobbelaere.github.io/sorting_networks_extended.html#N2L1D1 a = arr[i]; b = arr[j]; c = arr[k]; d = arr[l]; if (a < c) { at = a; ct = c; } else { at = c; ct = a; } if (b < d) { bt = b; dt = d; } else { bt = d; dt = b; } if (at < bt) b = bt; else b = at; if (ct < dt) c = ct; else c = dt; if (at < bt) arr[i] = at; else arr[i] = bt; if (b < c) { arr[j] = b; arr[k] = c; } else { arr[j] = c; arr[k] = b; } if (ct < dt) arr[l] = dt; else arr[l] = ct; } } // last insertion sort pass as final fixup for (let i = 1, j = 0; i < length; i++) { const a = arr[i]; for (j = i - 1; j >= 0 && arr[j] > a; j--) { arr[j + 1] = arr[j]; } if (++j < i) { arr[j] = a; } } return arr; }3a:T515,function leapfrog4Sort(arr) { const length = arr.length; const invφ = (2 / (1 + 5 ** 0.5)); // const invφ = (1 + 5 ** 0.5)/6; let gap = length * invφ | 0, a, b, c, d, l, h, i, j; while (gap > 6) { a = arr[0] < arr[1] ? arr[0] : arr[1]; b = arr[0] < arr[1] ? arr[1] : arr[0]; i = 2; j = i + gap; while (true) { c = arr[i] < arr[j] ? arr[i] : arr[j]; d = arr[i] < arr[j] ? arr[j] : arr[i]; if (c < b) { l = c; h = b; if (l < a) { b = a; a = l; } else {; b = l } if (h < d) { c = d; d = h; } else { c = h; } } arr[i - 2] = a; arr[j] = d; if (++j >= length) { // last-iteration fix-up: store b and c arr[i-1] = b; arr[i] = c; break; } a = b; b = c; i++; } gap = gap * invφ | 0; } // Final insertion sort pass to // fix any items still out of place // (can be modified to exploit the // expected distribution). for (i = 1; i < length; i++) { b = arr[i]; for ( j = i - 1; j >= 0 && (a = arr[j]) > b; j-- ) { arr[j + 1] = a; } if (++j < i) { arr[j] = b; } } return arr; }3b:T422,{ await visibility() const arrayBuilder = { Array: length => { const t = [0]; for (let i = 0; i < length; i++) t[i] = 0; return t; }, "Array(float)": length => { const t = [-0.0]; for (let i = 0; i < length; i++) t[i] = -0.0; return t; }, Uint8Array: length => new Uint8Array(length), Uint16Array: length => new Uint16Array(length), Uint32Array: length => new Uint32Array(length), Int8Array: length => new Int8Array(length), Int16Array: length => new Int16Array(length), Int32Array: length => new Int32Array(length), Float32Array: length => new Float32Array(length), Float64Array: length => new Float64Array(length) }[arrayType]; const t = randomValues(arrayBuilder(2**12))//.map(v => v >>> 0); const check = t.slice().sort((a, b) => a - b); const unsorted = t.slice(); const wrongIndices = []; leapfrogSortPrimes3(t); for (let i = 0; i < t.length; i++) { if (t[i] !== check[i]) wrongIndices.push(i);; } return {t, check, unsorted, wrongIndices} }3c:T5304,/** * Concept: flag sort, with a whole bunch of small optimizations: * * 1) We revert to insertion sort for small ranges (standard optimization, really) * * 2) Assume numbers fit in the smallest bit-width (8, 16, 24, 32, in that order) * until proven otherwise. Using this we can skip doing multiple passes on arrays * of (mostly) small numbers or sparse data. We also repeat this on sub-passes * so in the unlikely case that we have values where only the upper and lower * bits are set (that is, are like 0xFF0000FF), the middle passes are also skipped * * 3) The last pass is optimized by overwriting the last eight bits. Together with * the previous point this makes sorting values < 256 much faster. * * 4) With a bit of prep-work we can avoid swaps and directly write the values to * the correct bucket, saving on precious memory bandwidth. * * 5) We check if a range is already sorted and bail out early - this sometimes * benefits nearly sorted data as well, if it allows us to bail out early on * buckets that were already sorted * * 6) If one bucket contains all values in a single pass, we immediately recurse * to the next pass (speeds up cases where all values are large but only the last * bits have different values) * * 7?) TO TRY OUT: use Math.clz32 to create additional buckets that benefit * non-uniform distributions biased towards smaller numbers (e.g. if the * data set follows a Zipf distribution) * * I won't bother with implementing a version that handles the floating point or 64 bit case, * but in theory they could be radix sorted too (requires a copy to and from a typed array though) */ radixsort = { // Make the backing array for counting a continguous piece of memory, for cache purposes const backingArray32 = new Uint32Array(256 * 8); const liftedIndices = [0, 2, 4, 6].map(i => backingArray32.subarray(i * 256, (i + 1) * 256) ); const countingArrays32 = [1, 3, 5, 7].map(i => backingArray32.subarray(i * 256, (i + 1) * 256) ); const backingArray16 = new Uint16Array(backingArray32.buffer); const countingArrays16 = [2, 6, 10, 14].map(i => backingArray16.subarray(i * 256, (i + 1) * 256) ); const backingArray8 = new Uint8Array(backingArray32.buffer); const countingArrays8 = [4, 12, 20, 28].map(i => backingArray8.subarray(i * 256, (i + 1) * 256) ); function radixSortL32(array, left = 0, right = array.length, pass = 0) { // used to mask out the higher bits for later passes // pass == 0 for the full 32 bits, pass == 3 for 8 bits const mask = 0xFFFFFFFF >>> (8 * pass); let val = (array[left] & mask) >>> 0; let maxVal = val; let i = left; // It's practically free to check if the array is already sorted, // because we spend most time waiting for reading values of the // input array and updating the counting arrays let sorted = true, prev = val; if (maxVal < 0x100) { // 8 bit values const countingArray = countingArrays32[3]; countingArray.fill(0); for (; i < right; i++) { val = (array[i] & mask) >>> 0; // if val is bigger than 8 bits, the current index has to // fall through to the next appropriate bit width if (val > 0xFF) { // We really only care about whether or there is a value // that requires 8, 16, 24 or 32 bit, so "maxVal" is a // little misleading here. maxVal = val; break; } // can only reach this point if val < 256 countingArray[val]++; sorted = sorted && prev <= (prev = val); } } if (maxVal < 0x10000 && i < right) { // 16 bit values const countingArray = countingArrays32[2]; countingArray.fill(0); // if we already advanced a few points, we know that // these will all go into the first bucket countingArray[0] = i - left; for (; i < right; i++) { val = (array[i] & mask) >>> 0; if (val > 0xFFFF) { maxVal = val; break; } countingArray[(val >>> 8) & 0xFF]++; sorted = sorted && prev <= (prev = val); } } if (maxVal < 0x1000000 && i < right) { // 24 bit values const countingArray = countingArrays32[1]; countingArray.fill(0); countingArray[0] = i - left; for (; i < right; i++) { val = (array[i] & mask) >>> 0; if (val > 0xFFFFFF) { maxVal = val; break; } countingArray[(val >>> 16) & 0xFF]++; sorted = sorted && prev <= (prev = val); } } if (i < right) { // remaining 32 bit values const countingArray = countingArrays32[0]; countingArray.fill(0); countingArray[0] = i - left; while (i < right) { val = array[i++]; countingArray[val >>> 24]++; sorted = sorted && prev <= (prev = val); } } // Fast path for the sorted (sub)array case if (sorted) return array; // Now we do the actual sorting. Again, based on maxVal // we determine which approach we need if (maxVal < 0x100) { // for the last byte we can do a special micro-optimization: // instead of swapping, overwrite the lowest eight bits const countingArray = countingArrays32[3]; let i = left, j = left, n = 0, maskVal = array[i] - (array[i] & 0xFF); while (n < 256 && i < right) { j += countingArray[n++]; while (i < j) array[i++] = maskVal; maskVal++; } return array; } else if (maxVal < 0x10000) { // regardless of what pass we originally had, // we can adjust to the smallest max value. // Note that since maxVal is always based on // a masked value we can only skip passes, // not regress. pass = 2; } else if (maxVal < 0x1000000) { pass = 1; } const countingArray = countingArrays32[pass]; const shift = 24 - pass * 8; // Half-swap trick. We lift the first value of every non-empty bucket // This leaves "holes" in every bucket to be filled. Then we move the // first lifted value to the correct bucket, advance the idx of that // bucket to its next value, then move that value, and repeat until // we reach the end of a bucket. Then we repeat this with the next lifted // until we run out of lifted values to move. // This way we can avoid swaps: we can directly move values to the // correct bucket instead. const liftedValues = liftedIndices[pass]; let liftedVals = 0; // Re-use last pass array for storing the starting indices each bucket, // and convert the regular count array into marking the end-points // of every bucket (which effectively are the starting indices of // the next bucket). const indexArray = countingArrays32[3]; // Create indices array + lift values const range = right - left; if (range === countingArray[0]) { // If one bucket contains all values in the current range then // this pass will effectively do nothing. In that case we can // immediately recurse to the next pass, or immediately return // if pass === 3 since that implies it is already sorted. return pass === 3 ? array : radixSortL32(array, left, right, ++pass); } else if (countingArray[0] > 0) { liftedValues[liftedVals++] = array[left]; } indexArray[0] = left; for (let i = 1, prevCount = (countingArray[0] += left); i < 256; i++) { const count = countingArray[i]; if (range === count) { return pass === 3 ? array : radixSortL32(array, left, right, ++pass); } else if (count > 0) { liftedValues[liftedVals++] = array[prevCount]; } indexArray[i] = prevCount; prevCount += count; countingArray[i] = prevCount; } // The part where we actually move the values to the correct bucket for (let i = 0; i < liftedVals - 1; i++) { // We put one of the values in the hole in the // bucket it belongs, pick the next value from // that bucket (leaving a hole), put that value // into the hole in the bucket where it belongs, // and repeat this process until we reach the end // of a bucket. At that point we move onto the next // value in the "hole" aray, let val = liftedValues[i]; let bucket = (val >>> shift) & 0xFF; let idx = indexArray[bucket]++; let end = countingArray[bucket]; array[idx++] = val; while (idx < end) { val = array[idx]; bucket = (val >>> shift) & 0xFF; idx = indexArray[bucket]++; end = countingArray[bucket]; array[idx++] = val; } } // Here's a fun mini-optimization: if out of a total of N // buckets N-1 are "sorted", then the last bucket can only // contain values that should be there, and therefore must // be sorted as well. Therefore we can plug the last value // without checking the rest of the bucket. val = liftedValues[liftedVals - 1]; array[indexArray[(val >>> shift) & 0xFF]] = val; // Move on to the next pass pass++; for (let i = 0, sum = left; i < 256; i++) { const nextSum = countingArray[i]; if (sum < nextSum) { // insertion sort fallback for small ranges const range = nextSum - sum; if (range <= 50) { let j = sum + 1, k, v, v2, t; for (; j < nextSum; j+=2) { v = array[j], v2 = array[j - 1]; if (v < v2) { t = v; v = v2; v2 = t; } for (k = j - 2; k >= sum && (t = array[k]) > v; k--) { array[k + 2] = t; } array[k + 2] = v; for (; k >= sum && (t = array[k]) > v2; k--) { array[k + 1] = t; } array[k+1] = v2; } if (range > 1 && (range & 1)) { v = array[nextSum - 1]; k = nextSum - 2 while(k >= sum && (t = array[k]) > v) { array[k + 1] = t; k--; } if (++k < nextSum - 1) array[k] = v; } } else if (range < 256) { radixSortL8(array, sum, nextSum, pass); } else if (range < 0xFFFF) { radixSortL16(array, sum, nextSum, pass); } else { radixSortL32(array, sum, nextSum, pass); } } sum = nextSum; } return array; } // Range length < 65536 function radixSortL16(array, left = 0, right = array.length, pass = 0) { const mask = 0xFFFFFFFF >>> (8 * pass); let val = (array[left] & mask) >>> 0; let maxVal = val; let i = left; let sorted = true, prev = val; if (maxVal < 0x100) { const countingArray = countingArrays16[3]; countingArray.fill(0); for (; i < right; i++) { val = (array[i] & mask) >>> 0; if (val > 0xFF) { maxVal = val; break; } countingArray[val]++; sorted = sorted && prev <= (prev = val); } } if (maxVal < 0x10000 && i < right) { const countingArray = countingArrays16[2]; countingArray.fill(0); countingArray[0] = i - left; for (; i < right; i++) { val = (array[i] & mask) >>> 0; if (val > 0xFFFF) { maxVal = val; break; } countingArray[(val >>> 8) & 0xFF]++; sorted = sorted && prev <= (prev = val); } } if (maxVal < 0x1000000 && i < right) { const countingArray = countingArrays16[1]; countingArray.fill(0); countingArray[0] = i - left; for (; i < right; i++) { val = (array[i] & mask) >>> 0; if (val > 0xFFFFFF) { maxVal = val; break; } countingArray[(val >>> 16) & 0xFF]++; sorted = sorted && prev <= (prev = val); } } if (i < right) { const countingArray = countingArrays16[0]; countingArray.fill(0); countingArray[0] = i - left; while (i < right) { val = array[i++]; countingArray[val >>> 24]++; sorted = sorted && prev <= (prev = val); } } if (sorted) return array; if (maxVal < 256) { const countingArray = countingArrays16[3]; let i = left, j = left, n = 0, maskVal = array[i] - (array[i] & 0xFF); while (n < 256 && i < right) { j += countingArray[n++]; while (i < j) array[i++] = maskVal; maskVal++; } return array; } else if (maxVal < 0x10000) { pass = 2; } else if (maxVal < 0x1000000) { pass = 1; } const countingArray = countingArrays16[pass]; const shift = 24 - pass * 8; const liftedValues = liftedIndices[pass]; let liftedVals = 0; const indexArray = countingArrays16[3]; const range = right - left; if (range === countingArray[0]) { return pass === 3 ? array : radixSortL16(array, left, right, ++pass); } else if (countingArray[0] > 0) { liftedValues[liftedVals++] = array[left]; } indexArray[0] = 0; for (let i = 1, prevCount = countingArray[0]; i < 256; i++) { const count = countingArray[i]; if (range === count) { return pass === 3 ? array : radixSortL16(array, left, right, ++pass); } else if (count > 0) { liftedValues[liftedVals++] = array[left + prevCount]; } indexArray[i] = prevCount; prevCount += count; countingArray[i] = prevCount; } for (let i = 0; i < liftedVals - 1; i++) { let val = liftedValues[i]; let bucket = (val >>> shift) & 0xFF; let idx = indexArray[bucket]++; let end = countingArray[bucket]; array[left + idx++] = val; while (idx < end) { val = array[left + idx]; bucket = (val >>> shift) & 0xFF; idx = indexArray[bucket]++; end = countingArray[bucket]; array[left + idx++] = val; } } val = liftedValues[liftedVals - 1]; array[left + indexArray[(val >>> shift) & 0xFF]] = val; pass++; for (let i = 0, sum = left; i < 256; i++) { const nextSum = left + countingArray[i]; if (sum < nextSum) { const range = nextSum - sum; if (range <= 50) { let j = sum + 1, k, v, v2, t; for (; j < nextSum; j+=2) { v = array[j], v2 = array[j - 1]; if (v < v2) { t = v; v = v2; v2 = t; } for (k = j - 2; k >= sum && (t = array[k]) > v; k--) { array[k + 2] = t; } array[k + 2] = v; for (; k >= sum && (t = array[k]) > v2; k--) { array[k + 1] = t; } array[k+1] = v2; } if (range > 1 && (range & 1)) { v = array[nextSum - 1]; k = nextSum - 2 while(k >= sum && (t = array[k]) > v) { array[k + 1] = t; k--; } if (++k < nextSum - 1) array[k] = v; } } else if (range < 256) { radixSortL8(array, sum, nextSum, pass); } else { radixSortL16(array, sum, nextSum, pass); } } sum = nextSum; } return array; } // Array length less than 256 function radixSortL8(array, left = 0, right = array.length, pass = 0) { const mask = 0xFFFFFFFF >>> (8 * pass); let val = (array[left] & mask) >>> 0; let maxVal = val; let i = left; let sorted = true, prev = val; if (maxVal < 0x100) { const countingArray = countingArrays8[3]; countingArray.fill(0); for (; i < right; i++) { val = (array[i] & mask) >>> 0; if (val > 0xFF) { maxVal = val; break; } countingArray[val]++; sorted = sorted && prev <= (prev = val); } } if (maxVal < 0x10000 && i < right) { const countingArray = countingArrays8[2]; countingArray.fill(0); countingArray[0] = i - left; for (; i < right; i++) { val = (array[i] & mask) >>> 0; if (val > 0xFFFF) { maxVal = val; break; } countingArray[(val >>> 8) & 0xFF]++; sorted = sorted && prev <= (prev = val); } } if (maxVal < 0x1000000 && i < right) { const countingArray = countingArrays8[1]; countingArray.fill(0); countingArray[0] = i - left; for (; i < right; i++) { val = (array[i] & mask) >>> 0; if (val > 0xFFFFFF) { maxVal = val; break; } countingArray[(val >>> 16) & 0xFF]++; sorted = sorted && prev <= (prev = val); } } if (i < right) { const countingArray = countingArrays8[0]; countingArray.fill(0); countingArray[0] = i - left; while (i < right) { val = array[i++]; countingArray[val >>> 24]++; sorted = sorted && prev <= (prev = val); } } if (sorted) return array; if (maxVal < 0x100) { const countingArray = countingArrays8[3]; let i = left, j = left, n = 0, maskVal = array[i] - (array[i] & 0xFF); while (n < 256 && i < right) { j += countingArray[n++]; while (i < j) array[i++] = maskVal; maskVal++; } return array; } else if (maxVal < 0x10000) { pass = 2; } else if (maxVal < 0x1000000) { pass = 1; } const countingArray = countingArrays8[pass]; const shift = 24 - pass * 8; const liftedValues = liftedIndices[pass]; let liftedVals = 0; const indexArray = countingArrays8[3]; const range = right - left; if (range === countingArray[0]) { return pass === 3 ? array : radixSortL8(array, left, right, ++pass); } else if (countingArray[0] > 0) { liftedValues[liftedVals++] = array[left]; } indexArray[0] = 0; for (let i = 1, prevCount = countingArray[0]; i < 256; i++) { const count = countingArray[i]; if (range === count) { return pass === 3 ? array : radixSortL8(array, left, right, ++pass); } else if (count > 0) { liftedValues[liftedVals++] = array[left + prevCount]; } indexArray[i] = prevCount; prevCount += count; countingArray[i] = prevCount; } for (let i = 0; i < liftedVals - 1; i++) { let val = liftedValues[i]; let bucket = (val >>> shift) & 0xFF; let idx = indexArray[bucket]++; let end = countingArray[bucket]; array[left + idx++] = val; while (idx < end) { val = array[left + idx]; bucket = (val >>> shift) & 0xFF; idx = indexArray[bucket]++; end = countingArray[bucket]; array[left + idx++] = val; } } val = liftedValues[liftedVals - 1]; array[left + indexArray[(val >>> shift) & 0xFF]] = val; pass++; for (let i = 0, sum = left; i < 256; i++) { const nextSum = left + countingArray[i]; if (sum < nextSum) { const range = nextSum - sum; if (range <= 50) { // for (let i = sum + 1, j; i < nextSum; i++) { // const v = array[i]; // for (j = i - 1; j >= sum && array[j] > v; j--) { // array[j + 1] = array[j]; // } // if (++j < i) array[j] = v; // } let j = sum + 1, k, v, v2, t; for (; j < nextSum; j+=2) { v = array[j], v2 = array[j - 1]; if (v < v2) { t = v; v = v2; v2 = t; } for (k = j - 2; k >= sum && (t = array[k]) > v; k--) { array[k + 2] = t; } array[k + 2] = v; for (; k >= sum && (t = array[k]) > v2; k--) { array[k + 1] = t; } array[k+1] = v2; } if (range > 1 && (range & 1)) { v = array[nextSum - 1]; k = nextSum - 2 while(k >= sum && (t = array[k]) > v) { array[k + 1] = t; k--; } if (++k < nextSum - 1) array[k] = v; } } else { radixSortL8(array, sum, nextSum, pass); } } sum = nextSum; } return array; } return function radixsort(array, start = 0, end = array.length) { // // All benchmarks so far suggest that for arrays // // smaller than this the native sorts definitely win // if (array.length <= 200) { // if (Array.isArray(array)) array.sort((a, b) => a - b); // else array.sort(); // native TypedArray sort // return array; // } const range = end - start; if (range <= 40) { for (let i = start + 1, j; i < end; i++) { const v = array[i]; for (j = i - 1; j >= start && array[j] > v; j--) { array[j + 1] = array[j]; } if (++j < i) array[j] = v; } return array; } if (range < 256) return radixSortL8(array, start, end, 0); if (range < 0xFFFF) return radixSortL16(array, start, end, 0); return radixSortL32(array, start, end, 0); }; }3d:T2566,/** * 7?) TO TRY OUT: use Math.clz32 to create additional buckets that benefit * non-uniform distributions biased towards smaller numbers (e.g. if the * data set follows a Zipf distribution) */ radixsortCLZ = { // Make the backing array for counting a continguous piece of memory, for cache purposes const backingArray = new Uint32Array(256 * 8 + 24 + 16); const bArrays = [ 0, // counting array pass 0 256 + 24, // lifted indices pass 0 (256 + 24) * 2, // counting array pass 1 (256 + 24) * 2 + (256 + 16) * 1, // lifted indices pass 1 (256 + 24) * 2 + (256 + 16) * 2, // counting array pass 2 (256 + 24) * 2 + (256 + 16) * 1 + (256 + 8) * 1, // lifted indices pass 2 (256 + 24) * 2 + (256 + 16) * 2 + (256 + 8) * 2, // counting array pass 3 (256 + 24) * 2 + (256 + 16) * 2 + (256 + 8) * 2 + 256, // lifted indices array pass 3 (256 + 24) * 2 + (256 + 16) * 2 + (256 + 8) * 2 + 256 * 2 // lifted indices array pass 3 end ]; const countingArrays = [], liftedIndices = []; for (let i = 0; i < 8; i += 2) { const start = bArrays[i], mid = bArrays[i+1], end = bArrays[i+2]; countingArrays.push(backingArray.subarray(start, mid)); liftedIndices.push(backingArray.subarray(mid, end)); } const {clz32} = Math; function radixSortCLZ32(array, left = 0, right = array.length, pass = 0) { // used to mask out the higher bits for later passes // pass == 0 for the full 32 bits, pass == 3 for 8 bits const mask = 0xFFFFFFFF >>> (8 * pass); let val = (array[left] & mask) >>> 0; let maxVal = val; let i = left; // It's practically free to check if the array is already sorted, // because we spend most time waiting for reading values of the // input array and updating the counting arrays let sorted = true, prev = val; if (maxVal < 0x100) { // 8 bit values const countingArray = countingArrays[3]; countingArray.fill(0); for (; i < right; i++) { val = (array[i] & mask) >>> 0; // if val is bigger than 8 bits, the current index has to // fall through to the next appropriate bit width if (val > 0xFF) { // We really only care about whether or there is a value // that requires 8, 16, 24 or 32 bit, so "maxVal" is a // little misleading here. maxVal = val; break; } // can only reach this point if val < 256 countingArray[val]++; sorted = sorted && prev <= (prev = val); } } if (maxVal < 0x10000 && i < right) { // 16 bit values const countingArray = countingArrays[2]; countingArray.fill(0); // if we already advanced a few points, we know that // these will all go into the first bucket countingArray[0] = i - left; for (; i < right; i++) { val = (array[i] & mask) >>> 0; if (val > 0xFFFF) { maxVal = val; break; } countingArray[(val >>> 8) & 0xFF]++; sorted = sorted && prev <= (prev = val); } } if (maxVal < 0x1000000 && i < right) { // 24 bit values const countingArray = countingArrays[1]; countingArray.fill(0); countingArray[0] = i - left; for (; i < right; i++) { val = (array[i] & mask) >>> 0; if (val > 0xFFFFFF) { maxVal = val; break; } countingArray[(val >>> 16) & 0xFF]++; sorted = sorted && prev <= (prev = val); } } if (i < right) { // remaining 32 bit values const countingArray = countingArrays[0]; countingArray.fill(0); countingArray[0] = i - left; while (i < right) { val = array[i++]; countingArray[val >>> 24]++; sorted = sorted && prev <= (prev = val); } } // Fast path for the sorted (sub)array case if (sorted) return array; // Now we do the actual sorting. Again, based on maxVal // we determine which approach we need if (maxVal < 0x100) { // for the last byte we can do a special micro-optimization: // instead of swapping, overwrite the lowest eight bits const countingArray = countingArrays[3]; let i = left, j = left, n = 0, maskVal = array[i] - (array[i] & 0xFF); while (n < 256 && i < right) { j += countingArray[n++]; while (i < j) array[i++] = maskVal; maskVal++; } return array; } else if (maxVal < 0x10000) { // regardless of what pass we originally had, // we can adjust to the smallest max value. // Note that since maxVal is always based on // a masked value we can only skip passes, // not regress. pass = 2; } else if (maxVal < 0x1000000) { pass = 1; } const countingArray = countingArrays[pass]; const shift = 24 - pass * 8; // Half-swap trick. We lift the first value of every non-empty bucket // This leaves "holes" in every bucket to be filled. Then we move the // first lifted value to the correct bucket, advance the idx of that // bucket to its next value, then move that value, and repeat until // we reach the end of a bucket. Then we repeat this with the next lifted // until we run out of lifted values to move. // This way we can avoid swaps: we can directly move values to the // correct bucket instead. const liftedValues = liftedIndices[pass]; let liftedVals = 0; // Re-use last pass array for storing the starting indices each bucket, // and convert the regular count array into marking the end-points // of every bucket (which effectively are the starting indices of // the next bucket). const indexArray = countingArrays[3]; // Create indices array + lift values const range = right - left; if (range === countingArray[0]) { // If one bucket contains all values in the current range then // this pass will effectively do nothing. In that case we can // immediately recurse to the next pass, or immediately return // if pass === 3 since that implies it is already sorted. return pass === 3 ? array : radixSortCLZ32(array, left, right, ++pass); } else if (countingArray[0] > 0) { liftedValues[liftedVals++] = array[left]; } indexArray[0] = left; for (let i = 1, prevCount = (countingArray[0] += left); i < 256; i++) { const count = countingArray[i]; if (range === count) { return pass === 3 ? array : radixSortCLZ32(array, left, right, ++pass); } else if (count > 0) { liftedValues[liftedVals++] = array[prevCount]; } indexArray[i] = prevCount; prevCount += count; countingArray[i] = prevCount; } // The part where we actually move the values to the correct bucket for (let i = 0; i < liftedVals - 1; i++) { // We put one of the values in the hole in the // bucket it belongs, pick the next value from // that bucket (leaving a hole), put that value // into the hole in the bucket where it belongs, // and repeat this process until we reach the end // of a bucket. At that point we move onto the next // value in the "hole" aray, let val = liftedValues[i]; let bucket = (val >>> shift) & 0xFF; let idx = indexArray[bucket]++; let end = countingArray[bucket]; array[idx++] = val; while (idx < end) { val = array[idx]; bucket = (val >>> shift) & 0xFF; idx = indexArray[bucket]++; end = countingArray[bucket]; array[idx++] = val; } } // Here's a fun mini-optimization: if out of a total of N // buckets N-1 are "sorted", then the last bucket can only // contain values that should be there, and therefore must // be sorted as well. Therefore we can plug the last value // without checking the rest of the bucket. val = liftedValues[liftedVals - 1]; array[indexArray[(val >>> shift) & 0xFF]] = val; // Move on to the next pass pass++; for (let i = 0, sum = left; i < 256; i++) { const nextSum = countingArray[i]; if (sum < nextSum) { // insertion sort fallback for small ranges const range = nextSum - sum; if (range <= 50) { let j = sum + 1, k, v, v2, t; for (; j < nextSum; j+=2) { v = array[j], v2 = array[j - 1]; if (v < v2) { t = v; v = v2; v2 = t; } for (k = j - 2; k >= sum && (t = array[k]) > v; k--) { array[k + 2] = t; } array[k + 2] = v; for (; k >= sum && (t = array[k]) > v2; k--) { array[k + 1] = t; } array[k+1] = v2; } if (range > 1 && (range & 1)) { v = array[nextSum - 1]; k = nextSum - 2 while(k >= sum && (t = array[k]) > v) { array[k + 1] = t; k--; } if (++k < nextSum - 1) array[k] = v; } } else { radixSortCLZ32(array, sum, nextSum, pass); } } sum = nextSum; } return array; } return function radixsortCLZ(array, start = 0, end = array.length) { return radixSortCLZ32(array, start, end, 0); }; }3e:T56d,test_sort = { if (false) { const testInputs = [ new Uint32Array(0x10000), new Uint32Array(0x1000), new Uint32Array(0x100), new Uint32Array(0x10) ]; const originals = testInputs.map(arr => arr.slice()); const verifications = testInputs.map(arr => arr.slice()); let error; const samples = 1024; outer: for (let i = 0; i < samples; i++) { for (let j = 0; j < testInputs.length; j++) { const testInput = testInputs[j]; const original = originals[j]; const verification = verifications[j]; randomValues(testInput); original.set(testInput); original.sort(); radixsort(testInput); verification.set(testInput); verification.sort(); for (let j = 0; j < testInput.length; j++) { if (testInput[j] !== original[j]) { error = { sample: i, idx: j, o: original[j], t: testInput[j], v: verification[j], original, testInput, verification }; break; } } if (error) break outer; } if ((i&0x3F) === 0) yield `"${i + 1}/${samples} - no errors yet!`; } yield error || `no errors in ${samples} random runs!`; } else { yield "enable debugging to test"; } }3f:Taf4,radixsortU8 = { const countArray32 = new Uint32Array(256); const countArray16 = new Uint16Array(countArray32.buffer).subarray(0, 256); const countArray8 = new Uint16Array(countArray32.buffer).subarray(0, 256); const radixSortU8L8 = (u8array, left, right) => { let sorted = true; // count occurrences of each byte countArray8.fill(0); for(let i = left, prev = u8array[left]; i < right; i++) { const val = u8array[i]; countArray8[val]++; sorted = sorted && prev <= val; prev = val; } if (sorted) return; // Since we know we're only dealing with bytes, we can just overwrite the values: for(let i = 0, n = left, m = left; i < 256 && n < right; i++) { m += countArray8[i]; while(n < m) { u8array[n++] = i; } } }; const radixSortU8L16 = (u8array, left, right) => { let sorted = true; countArray16.fill(0); for(let i = left, prev = u8array[left]; i < right; i++) { const val = u8array[i]; countArray16[val]++; sorted = sorted && prev <= val; prev = val; } if (sorted) return; for(let i = 0, n = left, m = left; i < 256 && n < right; i++) { m += countArray16[i]; while(n < m) { u8array[n++] = i; } } }; const radixSortU8L32 = (u8array, left, right) => { let sorted = true; countArray32.fill(0); for(let i = left, prev = u8array[0]; i < right; i++) { const val = u8array[i]; countArray32[val]++; sorted = sorted && prev <= val; prev = val; } if (sorted) return; for(let i = 0, n = left, m = left; i < 256 && n < right; i++) { m += countArray32[i]; while(n < m) { u8array[n++] = i; } } }; return function radixsortU8(u8array, left = 0, right = u8array.length) { const range = right - left; if (range < 50) { let i = left + 1, j, v, v2, t; for (; i < right; i+=2) { v = u8array[i], v2 = u8array[i - 1]; if (v < v2) { t = v; v = v2; v2 = t; } for (j = i - 2; j >= left && (t = u8array[j]) > v; j--) { u8array[j + 2] = t; } u8array[j + 2] = v; for (; j >= left && (t = u8array[j]) > v2; j--) { u8array[j + 1] = t; } u8array[j+1] = v2; } if (range > 1 && (range & 1)) { v = u8array[right - 1]; j = right - 2 while(j >= left && (t = u8array[j]) > v) { u8array[j + 1] = t; j--; } if (++j < right - 1) u8array[j] = v; } } else if (range < 256) radixSortU8L8(u8array, left, right); else if (range < 0x10000) radixSortU8L16(u8array, left, right); else radixSortU8L32(u8array, left, right); return u8array; } }40:T54e,/* "Michael Herf has also discovered a good way to generalize this to floating point numbers: Reinterpret cast the float to a uint32, then flip every bit if the float was negative, but flip only the sign bit if the float was positive. The same trick works for doubles and uint64s. Michael Herf explains why this works in the linked piece, but the short version of it is this: Positive floating point numbers already sort correctly if we just reinterpret cast them to a uint32. The exponent comes before the mantissa, so we would sort by the exponent first, then by the mantissa. Everything works out. Negative floating point numbers however would sort the wrong way. Flipping all the bits on them fixes that. The final remaining problem is that positive floating point numbers need to sort as bigger than negative numbers, and the easiest way to do that is to flip the sign bit since it’s the most significant bit." https://probablydance.com/2016/12/27/i-wrote-a-faster-sorting-algorithm/ */ function radixF32(F32) { const U32 = new Uint32Array(F32.buffer); for (let i = 0; i < U32.length; i++) { const v = U32[i]; U32[i] = v & 0x80000000 ? v ^ 0xFFFFFFFF : v ^ 0x80000000; } radixsort(U32); for (let i = 0; i < U32.length; i++) { const v = U32[i]; U32[i] = v & 0x80000000 ? v ^ 0x80000000 : v ^ 0xFFFFFFFF; } return F32; }41:Tb14,// https://github.com/42milez/quicksort-with-webworker/blob/master/src/non-recursive.js function quickSortNR (array) { const {length} = array; if (length <= 40) { for(let i = 1, j; i < length; i++) { const v = array[i]; for (j = i - 1; j >= 0 && array[j] > v; j--) { array[j+1] = array[j] } if (++j < i) array[j] = v; } return array; } // size: size of stack // lStack: the stack for the left section index // rStack: the stack for the right section index // p: stack pointer const size = Math.floor(Math.LOG2E * Math.log(length)) + 1; const stack = new Uint32Array(size*2); let p = 2; stack[0] = 0; stack[1] = length - 1; while (p > 0) { p-- let right = stack[p--]; // an index of the right end of a section let left = stack[p]; // an index of the left end of a section // swap the values until a left end index and a right end index crosses while (left < right) { // // fall back to insertion sort for short ranges if (right - left <= 40) { const start = left; let j; while(++left <= right) { const v = array[left]; for (j = left; j > start && array[j-1] > v; j--) { array[j] = array[j-1]; } if (j < left) array[j] = v; } } else { let idx = Math.floor((left + right) / 2); // consider the value of the center index of a section as the pivot let pivot = array[idx]; let i = left; let j = right; // ------------------------------ // swap the values // ------------------------------ while (true) { while (array[i] < pivot) i++; // set the index forward if a value is less than the pivot while (pivot < array[j]) j--; // set the index forward if a value is greater than the pivot if (j <= i) break; const t = array[i]; array[i] = array[j]; array[j] = t; i++; j--; } // ------------------------------ // determine the next section which will be sorted // ------------------------------ // process the longer section next if (i - left < right - j) { // give priority to the left section if (left < i) { // stack the index of a right section // this section will be processed after sorting the left section stack[p++] = i; stack[p++] = right; } right = i - 1; // update a right section index } else { // give priority to the right section if (j < right) { stack[p++] = left; stack[p++] = j; } left = j + 1; } } } } return array; }42:Tb36,// https://github.com/42milez/quicksort-with-webworker/blob/master/src/non-recursive.js function quickSortNR2 (array) { const {length} = array; let i, j, t; if (length <= 40) { for (i = 1; i < length; i++) { t = array[i]; j = i; if (array[j-1] > t) { do { array[j] = array[--j]; } while (j > 0 && array[j-1] > t); array[j] = t; } } return array; } // size: size of stack // lStack: the stack for the left section index // rStack: the stack for the right section index // p: stack pointer const size = Math.floor(Math.LOG2E * Math.log(length)) + 1; const stack = new Uint32Array(size*2); stack[0] = 0; stack[1] = length - 1; let p = 2, right, left, pivot; while (p > 0) { p-- right = stack[p--]; // an index of the right end of a section left = stack[p]; // an index of the left end of a section // swap the values until a left end index and a right end index crosses while (left < right) { // fall back to insertion sort for short ranges if (right - left <= 40) { const start = left; while (++left <= right) { t = array[left]; j = left; if (array[j-1] > t) { do { array[j] = array[--j]; } while (j > start && array[j-1] > t); array[j] = t; } } } else { const pivot = array[(left + right) >>> 1]; // consider the value of the center index of a section as the pivot i = left; j = right; t; // ------------------------------ // swap the values // ------------------------------ while (true) { while (array[i] < pivot) i++; // set the index forward if a value is less than the pivot while (pivot < array[j]) j--; // set the index forward if a value is greater than the pivot if (j <= i) break; t = array[i]; array[i] = array[j]; array[j] = t; i++; j--; } // ------------------------------ // determine the next section which will be sorted // ------------------------------ // process the longer section next if (i - left < right - j) { // give priority to the left section if (left < i) { // stack the index of a right section // this section will be processed after sorting the left section stack[p++] = i; stack[p++] = right; } right = i - 1; // update a right section index } else { // give priority to the right section if (j < right) { stack[p++] = left; stack[p++] = j; } left = j + 1; } } } } return array; }43:T5f1,randomValues = { const {random} = Math; let x = random()*0x100000000 | 0; return function randomValues(typedArray, opts) { const { shift = 0, logdistributed = false, float = false } = opts || {}; // / * Observable seems to make crypto.getRandomValues() quite slow on Firefox */ // if (!Array.isArray(typedArray) && !shift && !logdistributed) { // const step = (1<<14)-1; // if (typedArray.length > step) { // for(let i = 0; i < typedArray.length; i += step) { // crypto.getRandomValues(typedArray.subarray(i, Math.min(i + step, typedArray.length))) // } // } else { // crypto.getRandomValues(typedArray); // } // return typedArray; // } // Use xorshift (good enough for this test) let _x = x; if (logdistributed) { let residue = 0; for(let i = 0; i < typedArray.length; i++){ residue = _x; for (let j = 4; j < 32; j += 4) { _x ^= _x << 13; _x ^= _x >> 17; _x ^= _x << 5; residue = residue & (_x | (0xFFFFFFFF >>> j)); } typedArray[i] = residue >>> shift; } } else { for(let i = 0; i < typedArray.length; i++){ _x ^= _x << 13; _x ^= _x >> 17; _x ^= _x << 5; typedArray[i] = _x >>> shift; } } x = _x; if (float) { for (let i = 0; i < typedArray.length; i++) { typedArray[i] += random(); } } return typedArray; }; }44:T558,// time_select = { // restart_time_select; // const testInputs = Array.from({length: 10000}, _ => new Uint32Array(1000)); // for (const input of testInputs) randomValues(input); // const timings = {radixselect: [], radixselectBranchless: [], radixsort: [], quickselect: []}; // let t0, t1; // for (let i = 0; i < 50; i++) { // const k = testInputs[0].lenght / i | 0; // for (const input of testInputs) randomValues(input); // t0 = performance.now(); // for (const input of testInputs) radixselect(input, k); // t1 = performance.now(); // timings.radixselect.push(t1 - t0); // for (const input of testInputs) randomValues(input); // t0 = performance.now(); // for (const input of testInputs) radixselectBranchless(input, k); // t1 = performance.now(); // timings.radixselectBranchless.push(t1 - t0); // // for (const input of testInputs) randomValues(input); // // t0 = performance.now(); // // for (const input of testInputs) radixsort(input); // // t1 = performance.now(); // // timings.radixsort.push(t1 - t0); // for (const input of testInputs) randomValues(input); // t0 = performance.now(); // for (const input of testInputs) quickselect(input, k); // t1 = performance.now(); // timings.quickselect.push(t1 - t0); // yield timings; // } // yield timings; // }45:T182c,radixselect = { const countArray = new Uint32Array(256); // Assumes we pass a Uint32Array (or any other array that only has values // that would fit in a Uint32Array) function _radixselect(array, k, left, right, pass) { // go from most significant byte to least significant byte let shift = 24 - pass*8; // Count occurrences of a particular masked/shifted byte value let max = 0; countArray.fill(0); for(let i = left; i < right; i++) { const val = array[i]; const bucket = (val >> shift) & 0xFF; countArray[bucket]++; if (val > max) max = val; } // If our values are small, the first few passes won't do anything if (pass < 3 && max < 0x100) { _radixselect(array, k, left, right, 3) return; } else if (pass < 2 && max < 0x10000) { _radixselect(array, k, left, right, 2) return; } else if (pass < 1 && max < 0x1000000) { _radixselect(array, k, left, right, 1) return; } let pivotBucket = 0; let sum = left; // Note that this overshoots - will be corrected for below do { sum += countArray[pivotBucket++]; } while(sum <= k); // We now know the "pivot" bucket in which our k value will // be found. However, unlike a regular sort, in the case of // n-selec we only care about whether all values on the left // of the pivot bucket are smaller than the pivot bucket, and // all values on the right are larger than the pivot bucket. // In other words: instead of sorting 256 buckets, we // can reduce that to a sort of Dutch Flag sort with the pivot // bucket as our middle value. // On top of that, because of our counting pass we also know // how many values are smaller, equal or larger than our pivot // bucket, so we can do a smarter-than average three-way sort // with half-swaps compared to the regular Dutch Flag sort. // Compared to a standard radix sort this three-way sort lets // us get away with less work in two ways: it reduces the // likelihood of having to swap values around from 255 time // out of 256 buckets to 2 out of 3 buckets (and one of those // is tiny, so it's closer to 1 out of 2). However, in the // process we introduce a three-way branch with a worst-case // branch prediction scenario, so it's not clear if this is // a net benefit (but see the branchless version below). // However, we also only have to recurse on the pivot bucket, // which saves on sorting 255 out of 256 buckets on the next // pass. When doing multiples passes this should lower total // overhead significantly. let pivotBucketStart = sum - countArray[--pivotBucket]; const pivotBucketEnd = sum; // If our pivot bucket spans the entire array, we can skip // the sorting step of this pass if (pivotBucketStart === left && pivotBucketEnd === right) { if (pass < 3) _radixselect(array, k, pivotBucketStart, pivotBucketEnd, pass+1); return; } let lowBucketStart = left; const lowBucketEnd = pivotBucketStart; let highBucketStart = pivotBucketEnd; const highBucketEnd = right; // create gaps in buckets so we can do "half-swaps" let holes = []; if (lowBucketStart < lowBucketEnd) { holes.push(array[lowBucketStart]); } if (pivotBucketStart < pivotBucketEnd) { holes.push(array[pivotBucketStart]); } if (highBucketStart < highBucketEnd) { holes.push(array[highBucketStart]); } // Here's a fun optimization: if two out of three // buckets are "sorted", then by definition the // third is as well. Hence the `> 1` comparison while (holes.length > 1) { // We put one of the values in the hole in the // bucket it belongs, pick the next value from // that bucket (leaving a hole), put that value // into the hole in the bucket where it belongs, // and repeat this process until we reach the end // of a bucket. At that point we move onto the next // value in the "hole" aray let val = holes.pop(); for(;;) { const bucket = (val >> shift) & 0xFF; if (bucket < pivotBucket) { array[lowBucketStart++] = val; if (lowBucketStart < lowBucketEnd) { val = array[lowBucketStart]; } else { break; } } else if (bucket > pivotBucket) { array[highBucketStart++] = val; if (highBucketStart < highBucketEnd) { val = array[highBucketStart]; } else { break; } } else { array[pivotBucketStart++] = val; if (pivotBucketStart < pivotBucketEnd) { val = array[pivotBucketStart]; } else { break; } } } } // clean-up: plug the last value back into the last hole const val = holes[0]; const bucket = (val >> shift) & 0xFF; if (bucket < pivotBucket) { array[lowBucketStart] = val; } else if (bucket > pivotBucket) { array[highBucketStart] = val; } else { array[pivotBucketStart] = val; } if (pivotBucketEnd - lowBucketEnd > 1 && pass < 3) { // insertion sort fallback for small ranges if (pivotBucketEnd - lowBucketEnd <= 40) { for(let i = lowBucketEnd + 1, j; i < pivotBucketEnd; i++) { const v = array[i]; for (j = i - 1; j >= lowBucketEnd && array[j] > v; j--) { array[j+1] = array[j] } if (++j < i) array[j] = v; } return; } else { _radixselect(array, k, lowBucketEnd, pivotBucketEnd, pass+1); } } } return function radixselect(array, k, left, right) { const _left = left === undefined ? 0 : left; const _right = right === undefined ? array.length : right; if (_left >= _right) { console.log(`\`left\` must be smaller than \`right\`! left: ${_left}, right: ${_right}`); return array; } if (array.constructor === Uint8Array) { return _radixselect(array, k, _left, _right, 3); } if (array.constructor === Uint16Array) { return _radixselect(array, k, _left, _right, 2); } _radixselect(array, k, _left, _right, 0); } }46:T13b6,radixselectBranchless = { const countArray = new Uint32Array(256); // Assumes we pass a Uint32Array (or any other array that only has values // that would fit in a Uint32Array) function _radixselect(array, k, left, right, pass) { // go from most significant byte to least significant byte let shift = 24 - pass*8; // Count occurrences of a particular masked/shifted byte value let max = 0; countArray.fill(0); for(let i = left; i < right; i++) { const val = array[i]; const bucket = (val >> shift) & 0xFF; countArray[bucket]++; if (val > max) max = val; } // If our values are small, the first few passes won't do anything if (pass < 3 && max < 0x100) { _radixselect(array, k, left, right, 3) return; } else if (pass < 2 && max < 0x10000) { _radixselect(array, k, left, right, 2) return; } else if (pass < 1 && max < 0x1000000) { _radixselect(array, k, left, right, 1) return; } let pivotBucket = 0; let sum = left; // Note that this overshoots - will be corrected for below do { sum += countArray[pivotBucket++]; } while(sum <= k); const pivotBucketStart = sum - countArray[--pivotBucket]; const pivotBucketEnd = sum; // If our pivot bucket spans the entire array, we can skip // the sorting step of this pass if (pivotBucketStart === left && pivotBucketEnd === right) { if (pass < 3) _radixselect(array, k, left, right, pass+1); return; } // create gaps in buckets so we can do "half-swaps" let holes = []; if (left < pivotBucketStart) { holes.push(array[left]); } if (pivotBucketStart < sum) { holes.push(array[pivotBucketStart]); } if (sum < right) { holes.push(array[sum]); } countArray[0] = left; // low bucket start countArray[1] = pivotBucketStart; // pivot bucket start countArray[2] = pivotBucketEnd // high bucket start countArray[3] = pivotBucketStart; // low bucket end countArray[4] = pivotBucketEnd // pivot bucket end countArray[5] = right; // high bucket end while (holes.length > 1) { let val = holes.pop(); // Yep, this is how we can do a branchless integer comparison in JavaScript. // Take a moment to marvel at this monstrosity. Came up with it myself. // (pivotbucket - bucket) is either: // a) negative if pivotbucket < bucket // b) zero if pivotbucket === bucket // c) positive if pivotbucket > bucket // >> 31 converts any positive value to 0, and any negative value to -1 // Combining those two insights, the "equation" below produces: // a) 0 if bucket < pivotbucket // b) 1 if bucket === pivotbucket // c) 2 if bucket > pivotbucket // All of this involves bitwise operations, which combined with good old // radix-sort based index arrays produces branchless swapping. It turns // out that avoiding a three-way branch makes this code notably faster // on Chrome, but not on Firefox (as of writing in Feb 2020). let bucket = (val >> shift) & 0xFF; bucket = -(((pivotBucket - bucket) >> 31) + ((pivotBucket - bucket - 1) >> 31)); let idx = countArray[bucket]++; let end = countArray[bucket+3]; array[idx++] = val; while(idx < end) { val = array[idx]; bucket = (val >> shift) & 0xFF; bucket = -(((pivotBucket - bucket) >> 31) + ((pivotBucket - bucket - 1) >> 31)); idx = countArray[bucket]++; end = countArray[bucket+3]; array[idx++] = val; } } // clean-up: plug the last value back into the last hole const val = holes[0]; const bucket = (val >> shift) & 0xFF; array[countArray[-(((pivotBucket - bucket) >> 31) + ((pivotBucket - bucket - 1) >> 31))]] = val; if (pivotBucketEnd - pivotBucketStart > 1 && pass < 3) { // insertion sort fallback for small ranges if (pivotBucketEnd - pivotBucketStart <= 40) { for(let i = pivotBucketStart + 1, j; i < pivotBucketEnd; i++) { const v = array[i]; for (j = i - 1; j >= pivotBucketStart && array[j] > v; j--) { array[j+1] = array[j] } if (++j < i) array[j] = v; } return; } else { _radixselect(array, k, pivotBucketStart, pivotBucketEnd, pass+1); } } } return function radixselectBranchless(array, k, left, right) { const _left = left === undefined ? 0 : left; const _right = right === undefined ? array.length : right; if (_left >= _right) { console.log(`\`left\` must be smaller than \`right\`! left: ${_left}, right: ${_right}`); return array; } if (array.constructor === Uint8Array) { return _radixselect(array, k, _left, _right, 3); } if (array.constructor === Uint16Array) { return _radixselect(array, k, _left, _right, 2); } _radixselect(array, k, _left, _right, 0); } }47:T46b,test_select = { if (false) { const testInput = new Uint32Array(100000); const original = testInput.slice(); const verification = testInput.slice(); let error; const samples = 1000; for (let i = 0; i < samples; i++) { const k = Math.random() * testInput.length | 0; randomValues(testInput); original.set(testInput); original.sort(); radixselectBranchless(testInput, k); verification.set(testInput); verification.sort() // make sure the values in the array are the same for(let j = 0; j < testInput.length; j++) { if (original[j] !== verification[j]) { error = {idx: j, o: original[j], t: testInput[j], v: verification[j], original, testInput, verification}; break; } } if (original[k] !== testInput[k]) { error = {k: k, o: original[k], t: testInput[k], v: verification[k], original, testInput, verification}; break; } if (error) break; yield `"${i+1}/${samples} - no errors yet!` } yield error || "no errors!" } else { yield "enable debugging to test"; } }48:[] 2f:{"id":"507ab3f69d80ffb9","slug":null,"title":"Beating the built-in sort, sometimes","thumbnail":"2b6dc05752abb58b4c4accacf75a60765114c365213d495bab178cc098d00150","access_level":"unlisted","create_time":"$D2020-02-07T16:28:08.548Z","update_time":"$D2026-01-16T13:54:00.568Z","view_time":null,"first_public_time":null,"has_unpublished_edits":null,"fork":false,"stars":0,"starred":false,"owner":{"type":"team","id":"3f83172cfde1e56a","login":"jobleonard","name":"Job van der Zwan","avatar_url":"https://avatars-next.observableusercontent.com/808373580aa09723ceabb9cb31d01ea6db287280b59eaa63618e259f5d28dd71","tier":"starter_2024"},"version":3414,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"d36034ddfb454bdd","login":"jobleonard","name":"Job van der Zwan","avatar_url":"https://avatars-next.observableusercontent.com/808373580aa09723ceabb9cb31d01ea6db287280b59eaa63618e259f5d28dd71","tier":null}],"members":[{"type":"individual","id":"d36034ddfb454bdd","login":"jobleonard","name":"Job van der Zwan","avatar_url":"https://avatars-next.observableusercontent.com/808373580aa09723ceabb9cb31d01ea6db287280b59eaa63618e259f5d28dd71","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":1,"collection":null,"type":"notebook","body":{"titling":"auto","title":"Beating the built-in sort, sometimes","cells":[{"id":591,"value":"md`# Beating the built-in sort, _sometimes_\n\n... as of writing on 3rd of June 2020\n\nBasically, if your array is large enough (starting somewhere between 500 and 1000 items on my machine, depending on the browser) and of the right data type (integer numbers), these radix sort implementations seem to beat the native sorts *for now*. Because they shouldn't and I'm sure some browser dev out there will fix this soon as a point of pride ;)\n\nNote: if you switch array type too often it may trigger a de-opt, producing slower results for the radix sort. To counter this, refresh the page.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1915,"value":"viewof arrayType = Radio(\n [\n \"Array\",\n \"Array(float)\",\n \"Uint8Array\",\n \"Uint16Array\",\n \"Uint32Array\",\n \"Float32Array\",\n \"Float64Array\"\n ],\n { label: html`Array Type:`, value: \"Array\" }\n)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1973,"value":"viewof inputWidth = Inputs.range(\n [8, 32],\n { label: html`Bit-width of input:`, value: 32, step: 1 }\n)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1986,"value":"viewof partial_checkbox = Toggle({\n label: html`Partial randomization:`\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1568,"value":"viewof time_sort_checkbox = Toggle({\n label: html`Start benchmark:`\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1825,"value":"arrayLength = (1 << 20);","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1823,"value":"totalArrays = 1 << Math.max(0, Math.clz32(arrayLength) - 11);","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1819,"value":"testInputs = {\n const arrayBuilder = {\n Array: length => {\n const t = [0];\n for (let i = 0; i < length; i++) t[i] = 0;\n return t;\n },\n \"Array(float)\": length => {\n const t = [-0.0];\n for (let i = 0; i < length; i++) t[i] = -0.0;\n return t;\n },\n Uint8Array: length => new Uint8Array(length),\n Uint16Array: length => new Uint16Array(length),\n Uint32Array: length => new Uint32Array(length),\n Int8Array: length => new Int8Array(length),\n Int16Array: length => new Int16Array(length),\n Int32Array: length => new Int32Array(length),\n Float32Array: length => new Float32Array(length),\n Float64Array: length => new Float64Array(length)\n }[arrayType];\n\n return Array.from({ length: totalArrays }, _ => arrayBuilder(arrayLength));\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1083,"value":"time_sort_sum = {\n let time_sort_sum = {}\n for (let key in time_sort) {\n let values = time_sort[key];\n if (values.length) {\n if (typeof values[0] !== \"number\"){\n time_sort_sum[key] = values\n } else {\n let sum = 0;\n for(const v of values) sum += v;\n time_sort_sum[key] = sum;\n }\n } else {\n time_sort_sum[key] = \"(skipped)\";\n }\n }\n return time_sort_sum;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":330,"value":"$31","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2641,"value":"$32","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3109,"value":"$33","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3312,"value":"$34","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2707,"value":"$35","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2795,"value":"$36","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3400,"value":"$37","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2951,"value":"$38","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3036,"value":"$39","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2943,"value":"$3a","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3211,"value":"$3b","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3357,"value":"function insertionSort(array) {\n const {length} = array;\n for (let i = 1, j; i < length; i++) {\n const v = array[i];\n for (j = i - 1; j >= 0 && array[j] > v; j--) {\n array[j + 1] = array[j];\n }\n if (++j < i) array[j] = v;\n }\n return array;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3167,"value":"function insertionSort2(array) {\n const {length} = array;\n for (let i = 1, j, v; i < length; i++) {\n v = array[i];\n j = i;\n if (array[j-1] > v) {\n do {\n array[j] = array[--j];\n } while (j > 0 && array[j-1] > v);\n array[j] = v;\n }\n }\n return array;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1591,"value":"$3c","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2607,"value":"$3d","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":714,"value":"$3e","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1951,"value":"$3f","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1889,"value":"$40","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1891,"value":"test_sortF32 = {\n if (false) {\n const testInput = new Float32Array(100000);\n const original = testInput.slice();\n const verification = testInput.slice();\n let error;\n const samples = 1000;\n for (let i = 0; i < samples; i++) {\n randomValuesF32(testInput);\n original.set(testInput);\n original.sort();\n radixF32(testInput);\n verification.set(testInput);\n verification.sort();\n for (let j = 0; j < testInput.length; j++) {\n if (testInput[j] !== original[j]) {\n error = {\n idx: j,\n o: original[j],\n t: testInput[j],\n v: verification[j],\n original,\n testInput,\n verification\n };\n break;\n }\n }\n if (error) break;\n yield `\"${i + 1}/${samples} - no errors yet!`;\n }\n yield error || \"no errors!\";\n } else {\n yield \"enable debugging to test\";\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":916,"value":"// https://01alchemist.com/projects/performance/sort/\nfunction quickSort(array, left, right) {\n // left = typeof left != \"number\" ? 0 : left;\n // right = typeof right != \"number\" ? array.length - 1 : right;\n // insertion sort fallback for small ranges\n if (right - left <= 40) {\n for(let i = left + 1, j; i < right; i++) {\n const v = array[i];\n for (j = i - 1; j >= left && array[j] > v; j--) {\n array[j+1] = array[j]\n }\n if (++j < i) array[j] = v; \n }\n return array;\n }\n // partition\n const pivot = array[(right + left) >>> 1];\n let i = left;\n let j = right;\n\n while (i <= j) {\n while (array[i] < pivot) { i++; }\n while (array[j] > pivot) { j--; }\n if (i <= j) { \n let t = array[i];\n array[i++] = array[j];\n array[j--] = t;\n }\n }\n // recurse\n if (left < i - 1) { quickSort(array, left, i - 1); }\n if (i < right) { quickSort(array, i, right); }\n\n return array;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1339,"value":"md`## Quicksort reference algorithms\n\nTaken from various places on the web, both cleaned up a little. Probably could be optimized a bit more too.\n\nhttps://01alchemist.com/projects/performance/sort/\n\nhttps://github.com/42milez/quicksort-with-webworker/blob/master/src/non-recursive.js\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":986,"value":"$41","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3114,"value":"$42","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3214,"value":"randomValues(new Uint8Array(1000))","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":423,"value":"$43","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1894,"value":"// Since we're probably want to have lots of random values in typed arrays,\n// we might as well operate directly on said arrays\nrandomValuesF32 = {\n let x = (Math.random() * 0x100000000) | 0;\n return function xorShiftF32Array(f) {\n const u = new Uint32Array(f.buffer);\n let _x = x;\n for (let i = 0; i < f.length; i++) {\n _x ^= _x << 13;\n _x ^= _x >> 17;\n _x ^= _x << 5;\n u[i] = (_x & 0x7fffff) | 0b111111100000000000000000000000;\n f[i] = (f[i] - 1) * 255;\n }\n x = _x;\n return f;\n };\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":0,"value":"md`# Radix Select\n\nNow that we have a radix sort, we can turn it into a select function by optimize it to only sort the buckets that are necessary! Floyd-Rivest is faster though, so this looks like it was a waste of time :(\n\n(This variant *might* be an original algorithm, but *probably* was already invented a long time ago)\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1118,"value":"viewof restart_time_select = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1112,"value":"time_select_sum = {\n let time_select_sum = {}\n for (let key in time_select) {\n let values = time_select[key];\n if (values.length) {\n let sum = 0;\n for(const v of values) sum += v;\n time_select_sum[key] = sum;\n } else {\n time_select_sum[key] = \"(skipped)\";\n }\n }\n return time_select_sum;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":161,"value":"$44","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":11,"value":"$45","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1373,"value":"$46","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1408,"value":"$47","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":40,"value":"quickselect = require('quickselect@2.0.0/quickselect.js')","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":14,"value":"testArray = Uint32Array.from({length: 5000000}, _ => Math.random() * 0x100000000 | 0)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1555,"value":"md`## TODO: Wasm experiments?\n\nThe main issue here is that we don't have fast access to javascript arrays in WASM - there is a fixed overhead of eiter copying an array to and from the memory in the WASM, or indirectly accessing it through getter and setter functions.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1524,"value":"// walt = await require('walt-compiler')","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1528,"value":"// bucketIdx = {\n// const source = `\n// export function bucketIdx(val: i32, shift: i32, pivotBucket: i32) : i32 {\n// const bucket : i32 = (val >> shift) & 0xFF;\n// return -(((pivotBucket - bucket) >> 31) + ((pivotBucket - bucket - 1) >> 31));\n// }\n// `;\n// const compiledBuffer = walt.compile(source).buffer();\n// return WebAssembly.instantiate(compiledBuffer, {}).then(result => {\n// return result.instance.exports.bucketIdx;\n// });\n// }","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1908,"value":"import { Toggle, Radio } from \"@observablehq/inputs\"","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W48","stdlib":"1"}} 30:"$2f:body"