Skip to content

Instantly share code, notes, and snippets.

@nns2009
Last active June 13, 2024 09:36
Show Gist options
  • Save nns2009/5349146b138537699a104ad52b6953cb to your computer and use it in GitHub Desktop.
Save nns2009/5349146b138537699a104ad52b6953cb to your computer and use it in GitHub Desktop.
Binary Tree Sort in 3 lines of code in JavaScript
// Watch https://youtu.be/KvYzGsz5vHA to see how I coded this with some commentary
let add = (n, v) => !n ? { v } : { ...n, [v < n.v]: add(n[v < n.v], v) }
let flat = n => !n ? [] : [...flat(n[!0]), n.v, ...flat(n[!1])]
let bsort = vs => flat(vs.reduce(add, null))
// 182 characters with nice formatting
let add=(n,v)=>!n?{v}:{...n,[v<n.v]:add(n[v<n.v],v)}
let flat=n=>!n?[]:[...flat(n[!0]),n.v,...flat(n[!1])]
let bsort=vs=>flat(vs.reduce(add,null))
// 147 characters with unnecessary whitespaces removed
/*
This method's computational complexity is:
O(N log N) on average and
O(N^2) in the worst case
You may further shorten the code by renaming functions,
e.g. add -> a, flat -> f, bsort -> b
but this would decrease redability, so I recommend not to do it
*/
const test=[34,3,13,5,8,13,21,21,55,34,3,3,2,1,34,8];
console.log(bsort(test));
console.log(test.sort((a,b)=>a-b));
// Basic testing code
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment