2d:null 2e:["$","title",null,{"children":"Sorting Algorithms | Zihou Ng | Observable"}] 33:T54e,md` Static visualizations provide an intuitive way to understand the behavior of sorting algorithms, here are some of the most typical ones. _This is a re-implementation of [cortesi/sortvis](https://github.com/cortesi/sortvis) on Observable. _ | Name | Average Time | Space | |------|------|-------| | [Insertion Sort](#idInsertion)| ${tex`O(n^2)`} | ${tex`O(1)`} | | [Quicksort](#idQuicksort) | ${tex`O(n \cdot \log(n))`} | ${tex`O(\log(n))`} | | [Mergesort](#idMergesort) | ${tex`O(n \cdot \log(n))`} | ${tex`O(n)`} | | [Shellsort](#idShellsort) | ${tex`O(n \cdot \log(n))`} | ${tex`O(1)`} | | [Heapsort](#idHeapsort) | ${tex`O(n \cdot \log(n))`} | ${tex`O(1)`} | | [Counting Sort](#isCountingsort) | ${tex`O(n+k)`} | ${tex`O(n+k)`} | | [Radix Sort](#idRadixSort) | ${tex`O(k \cdot n)`} | ${tex`O(k+n)`} | | [Bitonic Sort](#idBitonicSort) | ${tex`O(n \cdot \log(n)^2)`} | ${tex`O(\log(n))`} | | [Cycle Sort](#idCyclesort) | ${tex`O(n)`} | ${tex`O(1)`} | | [Timsort](#idTimsort) | ${tex`O(n \cdot \log(n))`} | ${tex`O(n)`} | | [Smooth Sort](#idSmoothSort) | ${tex`O(n \cdot \log(n))`} | ${tex`O(1)`} | Since the following ${tex`O(n^2)`} members take too much horizontal space, they are plotted separately. * [Selection Sort](#idSelection) * [Odd Even Sort](#idOddEvenSort) * [Cocktail Sort](#idCocktailSort) Click anywhere on the graph to reshuffle. `34:Tfb3,smoothSort = { class Shapes { static get LN() { return [ 1, 1, 3, 5, 9, 15, 25, 41, 67, 109, 177, 287, 465, 753, 1219, 1973, 3193, 5167, 8361, 13529, 21891, 35421, 57313, 92735, 150049, 242785, 392835, 635621, 1028457, 1664079, 2692537, 4356617, 7049155, 11405773, 18454929, 29860703, 48315633, 78176337, 126491971, 204668309, 331160281, 535828591, 866988873,1402817465, 2269806339, 3672623805 ]; } static leftChild(tree) { return tree[0] > 1 ? [tree[0] - 1, tree[1]] : undefined; } static rightChild(tree) { return tree[0] > 1 ? [tree[0] - 2, tree[1] + Shapes.LN[tree[0]-1]] : undefined; } static rootOffset(tree) { return tree[1] + Shapes.LN[tree[0]] - 1; } constructor() { this.trees = []; } push() { const n = this.trees.length; if (!this.canCollapse()) { if (n == 0) { this.trees.push([1, 0]); } else { const last = this.trees[n-1]; if (last[0] == 1) { this.trees.push([0, last[1] + 1]); } else { this.trees.push([1, last[1] + Shapes.LN[last[0]]]); } } } else { this.collapseLast(); } } pop() { const last = this.trees.pop(); if (last && last[0] > 1) { this.trees.push([last[0] - 1, last[1]]); this.trees.push([last[0] - 2, last[1] + Shapes.LN[last[0]-1]]); } } collapseLast() { this.trees.pop(); const last = this.trees.pop(); this.trees.push([last[0]+1, last[1]]); } canCollapse() { if (this.trees.length < 2) return false; const n = this.trees.length; const tree1 = this.trees[n-1], tree2 = this.trees[n-2]; return tree1[0] + 1 == tree2[0]; } } return values => { const n = values.length; const { copy, history } = prepare(values); let time = 1; const shapes = new Shapes(); function balance(tree) { let left = Shapes.leftChild(tree); let right = Shapes.rightChild(tree); if (left) { const p = Shapes.rootOffset(tree); const l = Shapes.rootOffset(left); const r = Shapes.rootOffset(right); if (copy[l] > copy[p] && copy[l] > copy[r]) { swap(l, p, ++time, copy, history); balance(left); } else if (copy[r] > copy[p]) { swap(r, p, ++time, copy, history); balance(right); } } } function shouldSwapHeaps(i, j) { const tree1 = shapes.trees[i]; const tree2 = shapes.trees[j]; const left = Shapes.leftChild(tree1); const right = Shapes.rightChild(tree1); const a = Shapes.rootOffset(tree1); const b = Shapes.rootOffset(tree2); if (copy[a] < copy[b]) { if (!left || copy[Shapes.rootOffset(left)] < copy[b]) { return !right || copy[Shapes.rootOffset(right)] < copy[b]; } else { return false; } } else { return false; } } function swapHeaps(i, j) { const a = Shapes.rootOffset(shapes.trees[i]); const b = Shapes.rootOffset(shapes.trees[j]); swap(a, b, ++time, copy, history); } function rectify(i) { if (shapes.trees.length == 1) { balance(shapes.trees[0]); } else if (shapes.trees.length > 1) { let cur = i; for (let j = i - 1; j >= 0;j--) { if (shouldSwapHeaps(cur, j)) { swapHeaps(cur, j); cur = j; } } balance(shapes.trees[cur]); } } for (let i = 0; i < n; i++) { shapes.push(); rectify(shapes.trees.length-1); } for (let i = 0; i < n; i++) { const before = shapes.trees.length; shapes.pop(); if (before < shapes.trees.length) { rectify(shapes.trees.length - 2); rectify(shapes.trees.length - 1); } } return { time, history }; } }35:T4c1,plot = (result, { maxTime, scales }) => { const svg = d3.select(DOM.svg(width, params.height)); const lines = svg.append('g').classed('lines', true) .attr('transform',`translate(0,${params.lineWidth})`); const data = makePointsData(result, maxTime); const polylinePoints = d => d[1].map(([t, y]) => `${scales.x(t)},${scales.y(y)}`).join(' '); lines.selectAll('.line').data(data) .join(enter => enter.append('g').call(g => { g.append('polyline').classed('line-border', true) .attr('points', polylinePoints) .attr('stroke', d3.hsl(0,0,0.1)) .attr('stroke-width', `${params.lineWidth+1.5}px`) .attr('stroke-linecap', 'round') .attr('stroke-linejoin', 'round') .attr('fill', 'none'); g.append('polyline').classed('line-fill', true) .attr('points', polylinePoints) .attr('stroke', d => scales.color(scales.values(d[0]))) .attr('stroke-width', `${params.lineWidth}px`) .attr('stroke-linecap', 'round') .attr('stroke-linejoin', 'round') .attr('fill', 'none'); })) .classed('line', true); svg.on('click', () => { mutable values = genValues(); }); return svg.node(); }36:[] 31:{"id":"b445dd50dec51620","slug":"sorting-algorithms","title":"Sorting Algorithms","thumbnail":"59a309ba236dca55ba39c7b06806e8dc1c6b94572addaa61e08b648292641e4b","access_level":"public","create_time":"$D2019-11-19T06:58:36.580Z","update_time":"$D2021-11-05T02:38:50.758Z","view_time":null,"first_public_time":"$D2019-11-22T11:09:56.620Z","has_unpublished_edits":null,"fork":false,"stars":80,"starred":false,"owner":{"type":"team","id":"7fad80bf128915e9","login":"stwind","name":"Zihou Ng","avatar_url":"https://avatars-next.observableusercontent.com/ff8a8f73ad220dcaec180c1e813951d692777837355004f062692b49042d2458","tier":"starter_2024","bio":"software engineer"},"version":2558,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"dbb85afd665c9e5e","login":"stwind","name":"Zihou Ng","avatar_url":"https://avatars-next.observableusercontent.com/ff8a8f73ad220dcaec180c1e813951d692777837355004f062692b49042d2458","tier":null,"bio":"software engineer"}],"members":[{"type":"individual","id":"dbb85afd665c9e5e","login":"stwind","name":"Zihou Ng","avatar_url":"https://avatars-next.observableusercontent.com/ff8a8f73ad220dcaec180c1e813951d692777837355004f062692b49042d2458","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":true,"trashed":false,"lapsed":null,"subscribed":null,"forks":19,"collection":{"id":"936bb5e9815c44d2","slug":"explorables","title":"Explorables","owner":{"id":"f35c755083683fe5","login":"observablehq","name":"Observable"}},"type":"notebook","body":{"titling":"auto","title":"Sorting Algorithms","cells":[{"id":0,"value":"idTop = md`# Sorting Algorithms`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":994,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":309,"value":"idInsertion = md`### Insertion Sort [▲](#idTop)`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":307,"value":"plot(results.insertion, settings)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":271,"value":"insertionSort = values => {\n const n = values.length;\n const { copy, history } = prepare(values);\n let time = 1;\n for (let i = 1;i < n;i++) {\n let j = i;\n while (j > 0 && copy[j] < copy[j-1]) {\n swap(j, --j, time++, copy, history);\n }\n }\n return { time, history };\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":642,"value":"idQuicksort = md`### Quicksort [▲](#idTop)`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":639,"value":"plot(results.quick, settings)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":492,"value":"quicksort = values => {\n const { copy, history } = prepare(values);\n let time = 1;\n \n function partition(left, right, pivot) {\n const v = copy[pivot];\n swap(pivot, --right, ++time, copy, history);\n for (let i = left; i < right; i++) {\n if (copy[i] <= v) {\n swap(i, left++, ++time, copy, history);\n }\n }\n swap(left, right, ++time, copy, history);\n return left;\n }\n \n function sort(left, right) {\n if (left < right - 1) {\n const pivot = partition(left, right, (left + right) >> 1);\n sort(left, pivot);\n sort(pivot + 1, right);\n }\n }\n \n sort(0, values.length);\n return { time, history }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":718,"value":"idMergesort = md`### Mergesort [▲](#idTop)`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":712,"value":"plot(results.merge, settings)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":676,"value":"mergesort = values => {\n const n = values.length;\n const { copy, history } = prepare(values);\n let time = 1;\n \n function sort(lo, hi) {\n if (lo == hi - 1) return;\n \n const mid = (lo + hi) >> 1;\n sort(lo, mid);\n sort(mid, hi);\n \n let i = lo, j = mid;\n while (i < j && j < hi) {\n if (copy[i] < copy[j]) {\n i++;\n } else {\n time++;\n const t = copy[j];\n \n for (let k = j; k > i;k--) {\n history.get(copy[k-1]).push([time, k]);\n copy[k] = copy[k-1];\n }\n \n history.get(t).push([time++, i]);\n copy[i] = t;\n i++; j++;\n }\n }\n }\n \n sort(0, n);\n return { time, history };\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1113,"value":"idShellsort = md`### Shellsort [▲](#idTop)`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1116,"value":"plot(results.shell, settings)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1096,"value":"shellsort = values => {\n const n = values.length;\n const { copy, history } = prepare(values);\n let time = 1;\n let h = 1;\n while (h < n / 3) h = h * 3 - 1;\n \n while (h >= 1) {\n for (let i = h;i < n; i++) {\n for (let j = i; j >= h && copy[j] < copy[j-h]; j -= h) {\n swap(j, j - h, ++time, copy ,history);\n }\n }\n \n h = Math.floor(h/3);\n }\n return { time, history };\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1152,"value":"idHeapsort = md`### Heapsort [▲](#idTop)`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1155,"value":"plot(results.heapsort, settings)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1123,"value":"heapsort = values => {\n const n = values.length;\n const { copy, history } = prepare(values);\n let time = 1;\n \n function sink(i, n) {\n let child = (i << 1) + 1;\n while (child < n) {\n if (child + 1 < n && copy[child] < copy[child+1])\n child++;\n\n if (copy[child] > copy[i]) {\n swap(i, child, time++, copy, history);\n } else {\n break;\n }\n i = child;\n child = (i << 1) + 1;\n }\n }\n \n for (let i = Math.floor(n/2);i >= 0;i--) {\n sink(i, n);\n }\n \n let end = n - 1;\n while (end > 0) {\n swap(0, end, time++, copy, history);\n sink(0, end--);\n }\n\n return { time, history };\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1172,"value":"isCountingsort = md`### Counting Sort [▲](#idTop)`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1178,"value":"plot(results.counting, settings)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1163,"value":"countingSort = values => {\n const n = values.length;\n const { copy, history } = prepare(values);\n let time = 1;\n \n for (let i = 0; i < n;i++) {\n if (copy[i] != i) {\n history.get(i).push([time++, i]);\n copy[i] = i;\n }\n }\n \n return { time, history };\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1372,"value":"idRadixSort = md`### Radix Sort [▲](#idTop)`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1508,"value":"plot(results.radix, settings)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1437,"value":"radixsort = values => {\n const { copy, history } = prepare(values);\n let time = 1;\n \n function sort(base) {\n const counts = Array(10).fill(0);\n for (const v of copy) {\n const key = Math.floor(v / base) % 10;\n counts[key]++;\n }\n \n for (let i = 1; i < 10; i++)\n counts[i] += counts[i-1];\n \n const cp = copy.slice();\n for (let i = cp.length - 1; i >= 0;i--) {\n const v = cp[i];\n const key = Math.floor(v / base) % 10;\n const pos = --counts[key];\n \n history.get(v).push([time++, pos]);\n copy[pos] = v;\n }\n }\n \n for (let exp = 1; exp < 100; exp *= 10)\n sort(exp);\n \n return { time, history };\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1670,"value":"idBitonicSort = md`### Bitonic Sort [▲](#idTop)`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1725,"value":"plot(results.bitonic, settings)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1723,"value":"bitonicSort = values => {\n const { copy, history } = prepare(values);\n let time = 1;\n \n function comp(i, j, asc) {\n if (copy[i] > copy[j] == asc) {\n swap(i, j, time++, copy, history);\n }\n }\n \n function merge(lo, n, asc) {\n if (n > 1) {\n const k = n / 2;\n for (let i = lo; i < lo + k; i++) {\n comp(i, i + k, asc);\n }\n merge(lo, k, asc);\n merge(lo + k, k, asc);\n }\n }\n \n function sort(lo, n, asc) {\n if (n > 1) {\n const k = n / 2;\n sort(lo, k, true);\n sort(lo + k, k, false);\n merge(lo, n, asc);\n }\n }\n \n sort(0, values.length, true);\n return { time, history };\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1673,"value":"md`\n\nRefererences\n\n* [Bitonic Sort - GeeksforGeeks](https://www.geeksforgeeks.org/bitonic-sort/)\n* [Bitonic sort](http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/bitonic/bitonicen.htm)\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1664,"value":"idCyclesort = md`### Cycle Sort [▲](#idTop)`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1784,"value":"plot(results.cycle, settings)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1781,"value":"cyclesort = values => {\n const { copy, history } = prepare(values);\n let time = 1;\n \n for (let i = 0; i < values.length; i++) {\n if (copy[i] != i) {\n let prev = copy[i], n = prev;\n \n for (; n != i; n = prev) {\n const tmp = copy[n];\n history.get(prev).push([time++, n]);\n copy[n] = prev;\n prev = tmp;\n }\n \n history.get(prev).push([time++, n]);\n copy[n] = prev;\n }\n }\n \n return { time, history };\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1667,"value":"md`\n\nReferences\n\n* [Cyclesort - a curious little sorting algorithm](https://corte.si/posts/code/cyclesort/index.html)\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1651,"value":"idTimsort = md`### Timsort [▲](#idTop)`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1964,"value":"plot(results.timsort, settings)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1960,"value":"timsort = values => {\n const n = values.length;\n const { copy, history } = prepare(values);\n let time = 1;\n const RUN = 4;\n \n function insertionSort(l, r) {\n for (let i = l + 1; i < r; i++) {\n let j = i;\n while (j > l && copy[j] < copy[j-1]) {\n swap(j, --j, time++, copy, history);\n }\n }\n }\n \n function merge(l, mid, r) {\n let i = l, j = mid;\n while (i < j && j < r) {\n if (copy[i] < copy[j]) {\n i++;\n } else {\n time++;\n const t = copy[j];\n \n for (let k = j; k > i;k--) {\n history.get(copy[k-1]).push([time, k]);\n copy[k] = copy[k-1];\n }\n \n history.get(t).push([time++, i]);\n copy[i] = t;\n i++; j++;\n }\n }\n }\n \n for (let i = 0; i < n; i += RUN) {\n insertionSort(i, i + RUN);\n }\n \n for (let size = RUN; size < n; size *= 2) {\n for (let i = 0; i < n; i += size * 2) {\n merge(i, i + size, Math.min(n, i + size * 2));\n }\n }\n \n return { time, history };\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1658,"value":"md`\nReferences\n\n* [Timsort - Wikipedia](https://en.wikipedia.org/wiki/Timsort)\n* [Visualising Sorting Algorithms: Python's timsort](https://corte.si/posts/code/timsort/index.html)\n * [Timsort - a study in grayscale](https://corte.si/posts/code/timsort-grayscale/index.html)\n* [The Case for Timsort - Richard Scheiwe - Medium](https://medium.com/@rscheiwe/the-case-for-timsort-349d5ce1e414)\n* [Timsort: The Fastest sorting algorithm for real-world problems.](https://dev.to/s_awdesh/timsort-fastest-sorting-algorithm-for-real-world-problems--2jhd)\n* [TimSort - GeeksforGeeks](https://www.geeksforgeeks.org/timsort/)\n* [timsort.txt](https://bugs.python.org/file4451/timsort.txt)\n* [[1805.08612] On the Worst-Case Complexity of TimSort](https://arxiv.org/abs/1805.08612)\n* [timsort/cpp-TimSort: A C++ implementation of timsort](https://github.com/timsort/cpp-TimSort)\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1837,"value":"idSmoothSort = md`### Smooth Sort [▲](#idTop)`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2387,"value":"plot(results.smooth, settings)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2283,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1840,"value":"md`\nThis implementation is a port of [bowd/smoothsort](https://github.com/bowd/smoothsort), originally written in Rust.\n\nReferences\n\n* [Smoothsort - Wikipedia](https://en.wikipedia.org/wiki/Smoothsort)\n* [Smoothsort Demystified](http://www.keithschwarz.com/smoothsort/)\n* [E.W.Dijkstra Archive: Smoothsort, an alternative for sorting in situ (EWD 796a)](https://www.cs.utexas.edu/users/EWD/transcriptions/EWD07xx/EWD796a.html)\n* [Smoothsort in Rust — BOWD](https://www.bowd.io/smoothsort-rust/)\n * [Leonardo numbers and Math I wish I knew — BOWD](https://www.bowd.io/leonardo-numbers)\n * [Leonardo heaps and how they work — BOWD](https://www.bowd.io/leonardo-heaps/)\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":100,"value":"idSelection = md`### Selection Sort [▲](#idTop)`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":24,"value":"plot(resultsN2.selection, settingsN2)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":71,"value":"selectionSort = values => {\n const n = values.length;\n const { copy, history } = prepare(values);\n let time = 1;\n \n for (let i = 0; i < n; i++) {\n let min = i;\n for (let j = i + 1;j < n; j++) { \n if (copy[j] < copy[min]) {\n min = j;\n }\n time++;\n }\n \n if (i != min) {\n swap(i, min, time, copy, history);\n }\n }\n return { time, history };\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2175,"value":"idOddEvenSort = md`### Odd Even Sort [▲](#idTop)`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2199,"value":"plot(resultsN2.oddeven, settingsN2)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2193,"value":"oddEvenSort = values => {\n const n = values.length;\n const { copy, history } = prepare(values);\n let time = 1, done = false;\n \n while (!done) {\n done = true;\n for (let start = 0; start < 2; start++) {\n for (let i = start; i < n - 1; i += 2) {\n time++\n if (copy[i] > copy[i+1]) {\n swap(i, i+1, time, copy, history);\n done = false;\n }\n }\n }\n }\n \n return { time, history };\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2179,"value":"idCocktailSort = md`### Cocktail Sort [▲](#idTop)`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2215,"value":"plot(resultsN2.cocktail, settingsN2)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2209,"value":"cocktailSort = values => {\n const n = values.length;\n const { copy, history } = prepare(values);\n let time = 1, swapped = true, start = 0, end = n;\n \n while (swapped) {\n swapped = false;\n for (let i = start; i < end; i++) {\n time++;\n if (copy[i] > copy[i+1]) {\n swap(i, i+1, time, copy, history);\n swapped = true;\n }\n }\n \n if (!swapped) break;\n swapped = false;\n \n end--;\n for (let i = end; i >= start; i--) {\n time++;\n if (copy[i] > copy[i+1]) {\n swap(i, i+1, time, copy, history);\n swapped = true;\n }\n }\n start++;\n }\n \n return { time, history };\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":262,"value":"md`## Misc`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2116,"value":"md`### Data`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":64,"value":"params = ({\n numValues: 16,\n lineWidth: 4.8,\n jitter: 0.5,\n height: 160,\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":19,"value":"mutable values = genValues()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2121,"value":"md`### Results`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":287,"value":"results = ({\n insertion: insertionSort(values),\n quick: quicksort(values),\n merge: mergesort(values),\n shell: shellsort(values),\n heapsort: heapsort(values),\n counting: countingSort(values),\n radix: radixsort(values),\n bitonic: bitonicSort(values),\n cycle: cyclesort(values),\n timsort: timsort(values),\n smooth: smoothSort(values),\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2095,"value":"settings = makePlotSettings(results)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2124,"value":"resultsN2 = ({\n selection: selectionSort(values),\n oddeven: oddEvenSort(values),\n cocktail: cocktailSort(values),\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2129,"value":"settingsN2 = makePlotSettings(resultsN2)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2113,"value":"md`### Utils`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":249,"value":"$35","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2091,"value":"makePlotSettings = results => {\n const maxTime = d3.max(Object.values(results), d => d.time) + 2;\n const scales = {\n values: d3.scaleLinear().domain([d3.min(values), d3.max(values)]).range([0.2, 0.8]),\n x: d3.scaleLinear().domain([0,maxTime]).range([0,width]),\n y: d3.scaleLinear().domain([0,values.length]).range([0,params.height]),\n color: d3.interpolateRdYlBu\n };\n return { maxTime, scales };\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":145,"value":"makePointsData = ({ history }, maxTime) => {\n function makePoints(entries) {\n const res = [entries[0]];\n for (let i = 1; i < entries.length; i++) {\n const a = entries[i-1], b = entries[i];\n res.push([b[0] - params.jitter, a[1]]);\n res.push([b[0] + params.jitter, b[1]]);\n }\n res.push([maxTime, res[res.length-1][1]]);\n return res;\n }\n \n return [...history.entries()].map(([k, v]) => [k, makePoints(v)]);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2035,"value":"genValues = () => d3.shuffle(d3.range(params.numValues))","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":321,"value":"prepare = values => ({ \n copy: values.slice(),\n history: values.reduce((map, x, i) => map.set(x, [[0, i]]), new Map())\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":647,"value":"swap = (i, j, time, copy, history) => {\n history.get(copy[i]).push([time, j]);\n history.get(copy[j]).push([time, i]);\n \n const t = copy[i];\n copy[i] = copy[j];\n copy[j] = t;\n }","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":53,"value":"md`## References\n\n* [cortesi/sortvis: Sorting algorithm visualisation with Cairo](https://github.com/cortesi/sortvis)\n * [Visualising Sorting Algorithms](https://corte.si/posts/code/visualisingsorting/index.html)\n* [Visualizing Algorithms](https://bost.ocks.org/mike/algorithms/)\n * [Quicksort V - bl.ocks.org](https://bl.ocks.org/mbostock/6dcc9a177065881b1bc4)\n* [Sorting algorithm - Wikipedia](https://en.wikipedia.org/wiki/Sorting_algorithm)\n* [Big-O Algorithm Complexity Cheat Sheet](https://www.bigocheatsheet.com/)\n* [SORTING](http://sorting.at/)\n* [BonzaiThePenguin/WikiSort](https://github.com/BonzaiThePenguin/WikiSort)\n* [ソートを極める！〜なぜソートを学ぶのか〜 - Qiita](https://qiita.com/drken/items/44c60118ab3703f7727f)\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W36","stdlib":"1"}} 32:"$31:body"